Loading... # LeetCode 128 最长连续序列：一个容易被忽略的 O(n) 陷阱 刷到 **LeetCode 128. 最长连续序列** 时，很多人都知道这道题的标准做法是使用哈希表。 题目要求我们在一个未排序的整数数组 `nums` 中，找出数字连续的最长序列长度，并且要求时间复杂度为 `O(n)`。 比如： ```c++ nums = [100, 4, 200, 1, 3, 2] ``` 最长连续序列是： ``` 1, 2, 3, 4 ``` 所以答案是： ``` 4 ``` 这道题的思路并不难，但有一个很隐蔽的坑： **用了 `unordered_set`，并不代表你的代码就一定是 `O(n)`。** 真正关键的问题是： > 构建完 `unordered_set` 之后，到底应该遍历原数组 `nums`，还是遍历去重后的 `unordered_set`？ 这两个写法看起来非常相似，但复杂度可能完全不同。 --- ## 一、标准思路 这道题的核心思路是： 1. 先把数组中的所有元素放入哈希集合 `unordered_set`； 2. 对于每个数字 `num`，判断它是不是一个连续序列的起点； 3. 如果 `num - 1` 不存在，说明 `num` 是起点； 4. 然后从 `num` 开始不断向后查找 `num + 1`、`num + 2`、`num + 3`； 5. 更新最长长度。 为什么要判断 `num - 1` 是否存在？ 因为我们只想从一个连续序列的起点开始统计。 比如： ``` nums = [1, 2, 3, 4] ``` 对于 `1` 来说，`0` 不存在，所以 `1` 是起点。 对于 `2` 来说，`1` 存在，所以 `2` 不是起点，应该跳过。 对于 `3` 来说，`2` 存在，也应该跳过。 对于 `4` 来说，`3` 存在，也应该跳过。 这样整段连续序列 `1, 2, 3, 4` 只会被扫描一次。 --- ## 二、推荐写法：遍历 unordered_set 正确写法如下： ```c++ class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> st(nums.begin(), nums.end()); int ans = 0; for (int num : st) { if (st.count(num - 1)) { continue; } int cur = num; while (st.count(cur)) { cur++; } ans = max(ans, cur - num); } return ans; } }; ``` 这段代码的关键在这里： ```c++ for (int num : st) ``` 我们遍历的是 `unordered_set`，而不是原数组 `nums`。 `unordered_set` 会自动去重，所以每个不同的数字只会被遍历一次。 比如： ```c++ nums = [1, 1, 1, 2, 3] ``` 构造出来的集合是： ```c++ st = {1, 2, 3} ``` 虽然原数组中有三个 `1`，但是集合中只有一个 `1`。 因此从 `1` 开始扫描连续序列时，只会扫描一次： ``` 1 -> 2 -> 3 ``` 这就是保证整体复杂度为 `O(n)` 的关键。 --- ## 三、容易踩坑的写法：遍历 nums 很多人可能会写成下面这样： ```c++ class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> st(nums.begin(), nums.end()); int ans = 0; for (int num : nums) { if (st.count(num - 1)) { continue; } int cur = num; while (st.count(cur)) { cur++; } ans = max(ans, cur - num); } return ans; } }; ``` 这段代码乍一看好像也没什么问题。 它也用了 `unordered_set`。 它也判断了： ```c++ if (st.count(num - 1)) { continue; } ``` 它也只从连续序列的起点开始向后扩展。 但是问题出在这里： ```c++ for (int num : nums) ``` 它遍历的是原数组 `nums`。 如果原数组中没有重复元素，这样写确实不会出太大问题。 但是题目并没有说数组中没有重复元素。 一旦存在重复元素，尤其是重复的连续序列起点，这段代码就可能发生大量重复计算。 --- ## 四、问题到底出在哪里？ 来看一个简单例子： ```c++ nums = [1, 1, 1, 2, 3] ``` 哈希集合是： ```c++ st = {1, 2, 3} ``` 最长连续序列是： ``` 1, 2, 3 ``` 答案是 `3`。 如果我们遍历 `unordered_set`，只会处理一次 `1`。 但是如果我们遍历原数组 `nums`，会发生什么？ 数组中有三个 `1`。 每次遇到 `1` 时，都会判断： ```c++ st.count(1 - 1) ``` 也就是： ```c++ st.count(0) ``` 因为 `0` 不存在，所以每一个 `1` 都会被认为是连续序列的起点。 于是程序会重复扫描三次： ``` 1 -> 2 -> 3 1 -> 2 -> 3 1 -> 2 -> 3 ``` 也就是说，同一段连续序列被重复统计了多次。 这就是复杂度退化的根源。 --- ## 五、一个更极端的例子 假设数组是： ```c++ nums = [1, 1, 1, 1, 1, 2, 3, 4, 5] ``` 集合是： ```c++ st = {1, 2, 3, 4, 5} ``` 如果遍历 `nums`，数组中有五个 `1`。 每个 `1` 都满足： ```c++ st.count(1 - 1) == 0 ``` 于是每个 `1` 都会触发一次完整扫描： ``` 1 -> 2 -> 3 -> 4 -> 5 1 -> 2 -> 3 -> 4 -> 5 1 -> 2 -> 3 -> 4 -> 5 1 -> 2 -> 3 -> 4 -> 5 1 -> 2 -> 3 -> 4 -> 5 ``` 如果重复起点很多，连续序列又很长，重复扫描的次数就会非常多。 最坏情况下，复杂度可能退化到接近： ``` O(n^2) ``` 所以问题不是出在 `unordered_set` 本身，而是出在： > 你虽然用了哈希表去重，但是遍历时又回到了没有去重的原数组。 --- ## 六、为什么遍历 unordered_set 可以保证 O(n)？ 再回到正确写法： ```c++ for (int num : st) ``` 因为 `st` 中的元素是去重后的。 对于每个连续序列，只有它的起点会真正进入 `while` 循环。 例如： ``` st = {1, 2, 3, 4, 100, 200} ``` 对于序列： ``` 1, 2, 3, 4 ``` 只有 `1` 会触发向后扫描。 `2`、`3`、`4` 都会因为前驱存在而跳过： ```c++ if (st.count(num - 1)) { continue; } ``` 所以每个数字最多被访问有限次，整体平均时间复杂度是 `O(n)`。 需要注意的是，这里的 `O(n)` 是基于 `unordered_set` 查询平均 `O(1)` 的前提。 --- ## 七、两种写法的本质区别 错误风险写法： ```c++ for (int num : nums) ``` 遍历原数组，可能重复处理相同数字。 推荐写法： ```c++ for (int num : st) ``` 遍历去重后的集合，每个数字只处理一次。 这就是两者的本质区别。 很多时候我们会以为： > 反正查找用的是 `unordered_set`，应该就是 O(n)。 但其实不一定。 `unordered_set` 只能保证查找快，不能保证你没有重复扫描。 真正保证 `O(n)` 的，是这两个条件同时成立： 1. 哈希表查询平均 `O(1)`； 2. 每个连续序列只从起点扫描一次，并且起点不会被重复处理。 如果遍历 `nums`，第二个条件就可能被破坏。 --- ## 八、如果一定要遍历 nums 怎么办？ 如果一定要遍历原数组 `nums`，也不是完全不可以。 只需要避免重复处理同一个起点即可。 比如可以额外使用一个集合记录已经处理过的起点： ```c++ class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> st(nums.begin(), nums.end()); unordered_set<int> usedStart; int ans = 0; for (int num : nums) { if (st.count(num - 1)) { continue; } if (usedStart.count(num)) { continue; } usedStart.insert(num); int cur = num; while (st.count(cur)) { cur++; } ans = max(ans, cur - num); } return ans; } }; ``` 这样可以避免重复起点被多次扫描。 但是这其实没有必要。 既然已经构造了 `unordered_set`，最简单、最自然、最不容易出错的方式就是直接遍历 `st`。 --- ## 九、一个代码细节：不需要使用引用 有些代码会写成： ```c++ for (int &num : nums) ``` 这里其实没有必要使用引用。 因为我们只是读取 `num`，并不会修改它。 对于 `int` 这种基础类型，直接写： ```c++ for (int num : nums) ``` 就可以了。 如果是比较大的对象，并且只读，可以使用： ```c++ for (const auto& x : container) ``` 但在这道题里，`int` 直接拷贝即可。 --- ## 十、最终推荐代码 推荐提交版本如下： ```c++ class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> st(nums.begin(), nums.end()); int ans = 0; for (int num : st) { if (st.count(num - 1)) { continue; } int cur = num; while (st.count(cur)) { cur++; } ans = max(ans, cur - num); } return ans; } }; ``` 也可以写成下面这种形式： ```c++ class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> st(nums.begin(), nums.end()); int ans = 0; for (int num : st) { if (st.count(num - 1)) { continue; } int len = 1; int cur = num; while (st.count(cur + 1)) { cur++; len++; } ans = max(ans, len); } return ans; } }; ``` 这两个版本本质上是一样的。 第一个版本用 `cur - num` 计算长度。 第二个版本用 `len` 记录长度。 --- ## 总结 LeetCode 128 这道题的坑点不是“要不要用 `unordered_set`”，而是： > 用了 `unordered_set` 之后，到底遍历谁？ 如果遍历的是去重后的集合： ```c++ for (int num : st) ``` 那么每个数字只会被处理一次，每个连续序列也只会从起点扫描一次，整体平均时间复杂度是 `O(n)`。 如果遍历的是原数组： ```c++ for (int num : nums) ``` 当数组中存在大量重复的序列起点时，同一段连续序列可能被反复扫描，复杂度可能退化到接近 `O(n^2)`。 所以这道题最稳妥的写法是： ```c++ unordered_set<int> st(nums.begin(), nums.end()); for (int num : st) { if (st.count(num - 1)) { continue; } int cur = num; while (st.count(cur)) { cur++; } ans = max(ans, cur - num); } ``` 一句话总结： > **LeetCode 128 的关键不是简单地使用哈希表，而是要遍历去重后的集合，避免重复起点导致重复扫描。** 猜你想看 PHP数据类型 vue组件数据共享 每日一学：PHP 中的array_column函数详解 JavaScript实现猜数字小游戏 正则表达式 每日一学：PHP 中的array_diff_uassoc函数详解 解决 Vue 打包过后 dist 文件夹过大 JS网页计算器 Go编码规范 JavaScript计时器 最后修改：2026 年 05 月 20 日 © 允许规范转载 赞 0 如果觉得我的文章对你有用，请随意赞赏
