128. 最长连续序列

难度：🟡 Medium | 标签：哈希、并查集 | 状态：⬜ LeetCode 链接

思路

全部丢进 unordered_set，O(1) 查询。 遍历每个数，只从「序列起点」开始往后数——起点的判据是 x-1 不在集合里。 保证每个数最多被访问 2 次（自己 + 作为某条链的一部分），总复杂度 O(n)。

代码

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int best = 0;
        for (int x : s) {
            if (s.count(x - 1)) continue;     // 不是起点，跳过
            int cur = x, len = 1;
            while (s.count(cur + 1)) { ++cur; ++len; }
            best = max(best, len);
        }
        return best;
    }
};

复杂度

• 时间 O(n)，空间 O(n)
• 朴素排序版 O(n log n)，本题要求 O(n)，必须用哈希

易错 / 回顾

• 「只从起点出发」是 O(n) 的关键，遗漏会变 O(n²)
• 遍历用 s 而不是 nums 可去重
• 注意 nums 可空，返回 0