128. Longest Consecutive Sequence

題目

給定一個陣列的數字，找出最長的連續sequence，e.g. [5, 6, 7, 8]

限制

• 0 <= nums.length <= $10^5$

• -$10^9$<= nums[i] <=$10^9$

思考Test case

• [ ] ⇒ 0

• [1, 3, 5, 7, 9] ⇒ 1

• [1, 1, 1, 1, 1, 1, 1] ⇒ 1

• [1, 4, 3, 2, 5] ⇒ 5

解題思路

1. 直覺上可使用sort之後，數字會被連續排列，只要不斷計算最長的連續長度即可

   1. 時間複雜度會是 O(logN)，題目要求至 O(N)

2. 使用Union Find，每拿到數字a便檢查a+1或a-1有沒有對應的group，有就union在一起

   1. 用 unordered_map<int, unordered_set>紀錄所有的father，並算出最長的set

   2. 操作複雜度為 O(logN)，還是會讓整體複雜度上升到 O(NlogN)

3. 更精簡的解法可以將所有數字放入set

   1. 只要不斷找出該數字的a + 1, a - 1存不存在set中便可以找出該連續數列長度

   2. 尋找連續數列的途中不斷記錄最長的長度

Coding思路

1. 將所有數字放入set去除重複的部分

2. 遍歷每個數字

   1. 不存在set中的數字便跳過(因為已經找過的數字會被移出set)

   2. 往數字 a + 1, a - 1去尋找set中連續數字直到上下界

   3. 拓展上下界的途中將數字從set中移除

   4. 連續數列長度為 upper_bound - lower_bound - 1，紀錄最大值

      1. upper_bound為連續數列最大值 + 1

      2. lower_bound為連續數列最小值 - 1

Solution

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());

        int ans = 0;
        for (const auto num : nums) {
            if (s.find(num) == s.end()) {
                continue;
            }

            int l = num - 1;
            while (s.find(l) != s.end()) {
                s.erase(l);
                l -= 1;
            }
            int u = num + 1;
            while (s.find(u) != s.end()) {
                s.erase(u);
                u += 1;
            }

            s.erase(num);
            ans = max(ans, u - l - 1);
        }
        return ans;
    }
};