哈希表

1.将所有数插入哈希表

2.枚举哈希表的每个数x

• 若x + 1存在，则看x + 2是否存在....直到找到第一个y使得x … y - 1都在数组中存在。此时连续序列长度是y - x

如何避免重复枚举呢？

我们每次枚举每一段连续序列的第一个数即可，即若x - 1不存在，则说明x是连续序列的第一个数。

$ 时间复杂度是O(N)，空间复杂度O(N) $

参考文献

lc究极班

AC代码

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int,int> mp;
        for (auto x : nums) mp[x] ++;
        int res = 0;
        for (auto item : mp){
            int x = item.first;
            if (mp.count(x - 1)) continue;
            else {
                int y = x;
                while (mp.count(y)) y ++;
                int cnt = y - x;
                res = max(res, cnt);
            }
        }
        return res;
    }
};