longest-consecutive-sequence

128. 最长连续序列

• https://leetcode.cn/problems/longest-consecutive-sequence/?envType=study-plan-v2&envId=top-100-liked

题解

要求 O(n)的算法。

这个我觉得比较难想，看了题解才知道怎么做。

关键在与找到连续序列的第一个数，判断 x 是否为第一个数的方法是查找是否存在 x-1, 使用 hashset 可以做到在 O(1)的时间内完成查找。

还有一个要注意的地方是遍历时要使用去重后的，不然复杂度就不是 O(n)了，有可能超时。

核心计算有两层循环，因为遍历的是去重后的，在外层循环里，每个数最多被访问一次，在内层循环中同样如此，所以复杂度为 2n,即 O(n)。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int res = 0;
        unordered_set<int> s;
        for(auto i:nums){
            s.insert(i);
        }

        for(auto i:s){
            if(s.count(i-1)){
                continue;
            }

            int cnt = 0;
            while(s.count(i)){
                cnt++;
                i++;
            }

            res = max(res,cnt);
        }
        return res;
    }
};