力扣(LeetCode)128. 最长连续序列(C++)

哈希集合

建立哈希集合，存入所有数。一次遍历数组，对每个数检查是否有前一个数，如果某个数没有前一个数，说明这个数是一个序列的起点，从这个数开始遍历得到序列长度，维护最大序列长度，即是本题答案。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> S;
        int ans = 0;
        for(auto &x:nums) S.insert(x);
        for(auto &x:nums){
            if(S.count(x)&&!S.count(x-1)){
                S.erase(x);
                int y = x+1;
                while(S.count(y)){
                    S.erase(y);
                    y++;
                }
                ans = max(ans,y-x);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

1. 时间复杂度 : $O(n)$ ， 建立哈希集合，以每个序列的起点开始，遍历整个序列的时间复杂度 $O(n)$ 。
2. 空间复杂度 : $O(n)$ ， 哈希集合的空间复杂度 $O(n)$ 。

AC