当前位置：首页 > ds >正文

06.最长连续序列

ds 2025/7/27 2:38:02

在这里插入图片描述

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

✅ 思路总结

用 unordered_set 存储所有数字，查找某个数是否存在的时间是 O(1)。
遍历每个数字 x，只从 x 是“连续序列起点”时才开始向右找：
- 也就是说，只有当 x - 1 不在集合中时，才从 x 开始数连续的。
从 x 开始，不断检查 x+1, x+2... 是否存在，一直到找不到为止。
每次记录最长的连续长度。

✅ 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 - xans = max(ans, y - x);}return ans;}
};

✅ 示例解释

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

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

遍历集合中的每个数：

当前数 `x`	是否起点（x-1不在集合）	找到的连续序列	序列长度
100	是	[100]	1
4	否（3在）	-	-
200	是	[200]	1
1	是	[1, 2, 3, 4]	4
3	否（2在）	-	-
2	否（1在）	-	-

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

✅ 时间 & 空间复杂度分析

时间复杂度：
- 遍历集合：O(n)
- 每个连续序列最多只遍历一次，即每个元素最多进入一次 while 循环
- 总体：O(n)
空间复杂度：
- 使用了一个 unordered_set 来存储所有元素 → O(n)

✅ 优点总结

优点	说明
✅ 高效	时间复杂度 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;}
};