8bbb8394bc2c4ddfb91488e74e651c98.png

【题目】：128. 最长连续序列

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> ss(nums.begin(), nums.end());
        int res = 0;
        for(int s : ss) {
            if(ss.find(s - 1) != ss.end()) {
                continue; // 说明s一定不是开头
            }
            // s是开头
            int y = s + 1;
            while(ss.find(y) != ss.end()) {
                y++;
            }
            res = max(y - s, res);
        }
        return res;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

可以把这题理解成，有好多条不同长度的线段，要找到最长那条线，只需要找到所有线的线段头，从头开始计算。
例如：**[100,4,101,200,1,3,2]**
本题一共有三条线段，分别是：100,101 和 200 和 1,2,3,4，先把这些数存在set中，遍历set。
如果遍历到2，先判断2前面是否还有数字，由于2前边还有，说明2不是开头，直接跳过后续操作。
如果遍历到1，1前边已经没有数字了，说明1就是开头，从头开始计算，看看这个线段长度是多长。
这里虽然是两个循环，但是内循环只有遍历到线段头的时候才会执行，所以时间复杂度为O(n)