06.最长连续序列

🚀 解法一：哈希表找“连续序列起点”

✅ 思路总结

1. 用 unordered_set 存储所有数字，查找某个数是否存在的时间是 O(1)。

2. 遍历每个数字 x，只从 x 是“连续序列起点”时才开始向右找：

   • 也就是说，只有当 x - 1 不在集合中时，才从 x 开始数连续的。

3. 从 x 开始，不断检查 x+1, x+2... 是否存在，一直到找不到为止。

4. 每次记录最长的连续长度。

✅ C++ 代码

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end()); // 把所有元素放入哈希集合
        int ans = 0;

        for (int x : st) { // 遍历哈希集合中的每个数
            if (st.contains(x - 1)) {
                // 如果存在 x-1，说明 x 不是连续序列的起点，跳过
                continue;
            }

            // 否则 x 是连续序列的起点
            int y = x + 1;
            while (st.contains(y)) {
                y++; // 一直向右找连续数字
            }

            // [x, y) 之间是连续序列，长度是 y - x
            ans = max(ans, y - x);
        }

        return ans;
    }
};

✅ 示例解释

示例 1：nums = [100, 4, 200, 1, 3, 2]

先构造集合 st = {1, 2, 3, 4, 100, 200}

遍历集合中的每个数：

最终答案就是最长的序列长度 4

✅ 时间 & 空间复杂度分析

• 时间复杂度：

  • 遍历集合：O(n)
  • 每个连续序列最多只遍历一次，即每个元素最多进入一次 while 循环
  • 总体：O(n)

• 空间复杂度：

  • 使用了一个 unordered_set 来存储所有元素 → O(n)

✅ 优点总结

✅ 通俗一句话总结

把所有数字丢进集合，只从那些“没有左邻居”的数出发，一路数右边的连续数，记录最长的长度！

🚀 解法二：哈希 + 并查集（更适合带区间合并需求的场景）

✅ 思路概括：

我们把每个数字当作并查集中的一个点，如果某个数 x 和 x+1 都存在，就将它们连起来。

最后统计并查集中最长的连通块长度，即为最长连续序列长度。

✅ C++代码

class Solution {
public:
    unordered_map<int, int> parent;   // 存储每个数的父节点
    unordered_map<int, int> size;     // 存储以某个节点为根的集合大小（即连续序列长度）

    // 查找函数：带路径压缩
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }

    // 合并两个集合
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;  // 已在同一个集合中

        // 合并：把小的合并到大的
        parent[rootX] = rootY;
        size[rootY] += size[rootX];
    }

    int longestConsecutive(vector<int>& nums) {
        // 初始化并查集
        for (int x : nums) {
            if (parent.count(x)) continue; // 避免重复插入重复元素
            parent[x] = x;
            size[x] = 1;

            // 如果相邻的数存在，就合并
            if (parent.count(x - 1)) unite(x, x - 1);
            if (parent.count(x + 1)) unite(x, x + 1);
        }

        int ans = 0;
        for (auto& [k, v] : size) {
            ans = max(ans, v); // 所有集合中找最大值
        }
        return ans;
    }
};

✅ 示例说明

以 nums = [100, 4, 200, 1, 3, 2] 为例：

• 插入 100 → 单独成一个集合。
• 插入 4 → 单独成集合。
• 插入 200 → 单独成集合。
• 插入 1 → 单独成集合。
• 插入 3 → 发现 4 存在 → 合并 3 和 4。
• 插入 2 → 发现 1 和 3 存在 → 合并 2 和 1，再合并 2 和 3，最终变成 [1,2,3,4] 一个大集合，大小为 4。

✅ 复杂度分析

• 时间复杂度：近似 O(n)（每次 find 和 union 的复杂度为 O(α(n))，近似常数）。
• 空间复杂度：O(n)

✅ 对比第一种解法