复杂度剖析)
刷 LeetCode 的人基本都有一个感受：有些题是“看着简单，做了才知道水多深”，128 题《最长连续序列》就是典型。你拿到题的第一反应大概率是“排序然后数一遍”，但题目末尾一句“要求时间复杂度 O(n)”直接堵死了这条最顺的路。这道题被标为 Medium 不是因为它有多难写，而是因为它逼着你跳出排序思维，换一个角度理解“连续”这件事。
这篇文章就围绕这道题做一次完整拆解：从题目约束反推可行方案、哈希表解法为什么能做到 O(n)、代码里有哪些一不留神就踩的边界坑，以及面试时怎么把复杂度论证讲得让面试官点头。不论你是刚开始刷题的新手，还是准备面试想补一下复杂度分析能力的老手，这篇都能给你一些题解里没细讲的视角。
1. 先看透题目的限制条件：O(n) 到底卡掉了哪些常见思路
1.1 题目描述与“连续序列”的准确含义
题目给定一个未排序的整数数组nums，要找出数字连续的最长序列的长度。注意这里说的是“序列”而不是“子数组”，这两者有本质区别。
举个例子：[100, 4, 200, 1, 3, 2]，答案是 4，对应的是1, 2, 3, 4。看数组本身，这四个数并不在相邻位置上，它们是散落在数组各处的。所以这道题根本不是“连续子数组”问题，而是“集合中能连成一条最长的整数链”的问题。你不需要保持它们在原数组中的相对顺序，只需要判断这些数字在数值上能不能首尾相接。
这个歧义其实是很多人第一次做错的原因——有人会下意识去写滑动窗口、双指针，结果发现题目要求跟“子数组连续”完全不是一回事。一旦确认了“无序集合中找最长整数链”这个本质，后面的算法选型就有了明确方向。
1.2 为什么排序解法第一个被排除
排序是最容易想到的思路：把数组排好序，从头到尾扫一遍，遇到相邻元素差为 1 就累加长度，否则重置。这个思路完全正确，但它的问题是复杂度。
Java 里Arrays.sort用的 Dual-Pivot Quicksort，平均时间复杂度 O(n log n)；Python 的sorted()是 Timsort，同样是 O(n log n)。不管底层怎么优化，只要是基于比较的排序，就不可能突破 O(n log n) 的下界。而题目明确要求 O(n)，所以排序方案从第一步就要被排除。
这里有个很关键的启发：如果一道题要求 O(n) 时间，但它涉及的输入是普通的整数数组，那基本意味着你只能做“常数次遍历”，或者借助哈希表让“查找”变成 O(1)。128 题正是后一种思路——用空间换时间。
提示：排序思路被排除不是因为它错，而是因为它不满足题目约束。如果你是在真实业务里解决类似问题，数组很短或没有复杂度要求时，排序反而是最稳、最不容易出 bug 的方案。刷题时我们追求最优复杂度，但工程里“足够好”往往比“最优”更重要。
1.3 暴力枚举的复杂度天花板
排除了排序，另一个很自然的方向是暴力：对每个数字，往前往后查它相邻的数在不在数组里。用HashSet存下所有数字，查找 O(1)，然后对每个数向后不断尝试num + 1、num + 2……最后统计最长链。
这个方案比排序还直观，代码不到 20 行，但它的复杂度有一个隐蔽的陷阱。
考虑一个数组[0, 1, 2, 3, ..., 9999]，你从 0 开始能一路数到 9999，从 1 开始也能数到 9999，从 2 开始也能……也就是说，如果对每个元素都从头向后扫描，总操作次数是 9999 + 9998 + 9997 + ...，也就是 O(n²)。在 LeetCode 的数据规模下（最多 10^5 个元素），这里会产生约 5×10^9 次操作，直接 TLE。
所以“用哈希表加速查找”只是第一步，“避免重复遍历”才是把复杂度从 O(n²) 降下来 O(n) 的关键。而 128 题的哈希表解法，本质上就是在回答一个问题：到底哪些数字值得作为“起点”发起扫描？
2. 哈希表解法完整拆解：从一个“起点”的判定说起
2.1 核心思路：只从序列起点发起遍历
既然暴力解的问题是“每个数字都从头扫一遍”，那优化的方向就很明确：只从每个连续序列的起点开始扫描，非起点一律跳过。
怎么判断一个数是不是连续序列的起点？很简单：如果num - 1不在数组里，那num就是某个序列的起点；如果num - 1存在，那num一定是某个更长链的中间节点，从它开始数只会得到一段“残缺”的链，这个数轮不到它当起点。
拿[100, 4, 200, 1, 3, 2]来说：
- 100：
99不在，99 不可能是起点？不对，100 是起点，因为没有 99。 - 4：
3在，所以 4 不是起点，跳过。 - 200：
199不在，200 是起点，但向后只有 200 一个，长度 1。 - 1：
0不在，1 是起点，向后可以找到 2、3、4，长度 4。 - 3：
2在，跳过。 - 2：
1在，跳过。
只有起点才会进入 while 循环往后数。这样一来，每个数最多被发起一次扫描，而扫描会覆盖一条完整的链，链上的每个元素又只会被扫描一次。后面会详细证明这就是 O(n)。
2.2 关键代码与逐行解析
这是 Java 版的标准实现，也是我推荐面试时手写的版本：
class Solution { public int longestConsecutive(int[] nums) { Set<Integer> set = new HashSet<>(); for (int num : nums) { set.add(num); } int longestStreak = 0; for (int num : set) { // 只从序列起点开始统计 if (!set.contains(num - 1)) { int currentNum = num; int currentStreak = 1; while (set.contains(currentNum + 1)) { currentNum += 1; currentStreak += 1; } longestStreak = Math.max(longestStreak, currentStreak); } } return longestStreak; } }Python 版也是一样的逻辑：
class Solution: def longestConsecutive(self, nums: List[int]) -> int: num_set = set(nums) longest = 0 for num in num_set: if num - 1 not in num_set: cur = num length = 1 while cur + 1 in num_set: cur += 1 length += 1 longest = max(longest, length) return longest代码里最关键的一行就是if (!set.contains(num - 1))。它看似只是一个简单的“剪枝”判断，实际上决定了整个算法能不能达到 O(n)。如果没有这行，代码就退化成 1.3 节说的暴力枚举，复杂度直接回到 O(n²)。
2.3 遍历 HashSet 还是遍历原始数组？
一个很多人注意到但没想透的细节：外层 for 循环遍历的是set，而不是原始数组nums。这有什么区别？
先说结论：遍历set更好，但遍历原始数组也不会错，只是可能做重复工作。原因在于原始数组里可能出现重复元素。假设数组是[0, 0, 1, 2, 3]，如果遍历原始数组，第一个 0 会触发一次完整扫描，第二个 0 又会触发一次一模一样的扫描。两次结果相同，浪费了时间。而set天然去重，每个数字只处理一次。
做复杂度分析时，遍历set有一个额外的好处：理论证明过程更干净。因为你去重了，set的大小最多是 n，每个元素在后边的 while 里也只会被访问一次，整个分析的思路非常顺。面试时讲这个细节，面试官会觉得你是真的理解，而不是背代码。
3. 时间复杂度论证：为什么整个流程严格是 O(n)
3.1 直觉上的疑虑：while 嵌套在 for 里面，怎么会是 O(n)？
这是 128 题评论区问得最多的问题。光看代码结构，外层 for 循环套内层 while 循环，标准的双重循环模样，怎么看都不像 O(n)。
关键点在于：内层 while 的总执行次数是有上限的，不是每个外层元素都触发一次完整的 while 循环。上面的if判断把大量元素挡在了 while 之外，只有序列起点才进入 while，而且每个起点对应的 while 扫描到的元素，在后面不会再被其他起点扫描到。
举个例子。假设数组里有[1, 2, 3, 4, 5, 100]，起点是 1 和 100。1 会一直扫到 5，把 2、3、4、5 都访问一遍。当外层循环遍历到 2、3、4、5 时，它们因为num - 1存在而被跳过，根本不会重复访问。100 单独一个，扫描一次就结束。
所以 while 循环里每个元素其实只会被访问一次，整个算法的总操作次数大概是“外层遍历 n 次 + 内层累计扫描 n 次”，也就是 O(2n)，还是 O(n)。
3.2 摊还分析视角：每个元素只被“起点循环”访问一次
如果要更严谨地论证，可以用摊还分析（Amortized Analysis）来看。
把整个算法的操作分成两类：
- 第一类是外层 for 循环里对每个元素做
contains(num - 1)判定的代价，这个是一个 O(1) 的哈希查找，总共 n 次，所以这部分一共 O(n)。 - 第二类是 while 循环里
contains(currentNum + 1)的代价。每次 while 循环都从某个起点开始，一直向后扩展到序列结束。你可以把一个 while 循环看成“访问了这条连续链上的所有元素”。由于每条链只被它的起点触发一次，链上的每个元素最多被访问一次，所以所有 while 循环加起来的访问次数，不超过数组中去重后元素的总数 n。
两部分加起来，总操作次数是 2n 左右，常数级别的 2，依旧是 O(n)。
关键点：while 循环并不是对每个元素都执行一遍“完整扫描”，二而是对“每个连续链”执行一遍扫描。链的总长度不超过 n，所以总耗时不超过 2n。
3.3 去掉起点判断之后的最坏情况
为了看清if (!set.contains(num - 1))到底有多重要，可以做一个对照实验：把这一行删掉，直接对每个数发起 while 扫描。
for (int num : set) { int cur = num; int len = 1; while (set.contains(cur + 1)) { cur++; len++; } longest = Math.max(longest, len); }这个版本接收一个已经排好序的数组[0, 1, 2, ..., 9999]，会发生什么？第一次循环从 0 开始扫到 9999，第二次从 1 扫到 9999，第三次从 2 扫到 9999……总共扫描次数大概是 10000 + 9999 + 9998 + ... = 约 5×10^7 次。如果 n 是 10^5，这个数字会到 5×10^9 次，超时是板上钉钉的。
这个对比能很直观地告诉你：起点判断不是“优化技巧”，而是这个算法能成立的根本保证。面试时如果被问到“为什么不是 O(n²)”，用这个例子讲最容易让对方理解。
4. 编码细节与边界条件：从“思路对”到“提交通过”
4.1 空数组、全重复元素与负数这些边界
很多题解讲完主流程就结束了，但实际提交的时候，边界条件才是决定你“一次过”还是“反复修”的因素。我按踩坑频率列一下：
空数组：nums长度为 0 时，set为空，外层循环不执行，longestStreak保持 0，直接返回 0。没有任何特殊处理也能通过。
单元素数组：比如[5]，起点判断!set.contains(4)成立，while 检查 6 不在，长度是 1。所以初始值设 0 而不是 1 是安全的，因为单元素会正常统计出 1。
全相同元素：比如[2, 2, 2]，转成set后只剩一个 2，最终结果是 1 而不是 3。这是符合题目定义的，因为“连续序列”要求的是数字连续，不是元素重复出现多次。
负数元素：比如[-3, -2, -1, 0, 1]，哈希表对负数没有任何特殊限制，处理方式与正数完全一致。这里容易出的问题是在别的解法里用数组当下标时的边界错乱，但用HashSet不存在这个问题。
数组元素上下界：LeetCode 原题约束在 -10^9 到 10^9，如果用HashSet完全不用关心这个范围，但如果你优化时想用布尔数组或者位图来模拟 HashSet，就得先做偏移处理，因为这些值不可能直接当下标。
4.2 常见错误实现与超时原因
我在 LeetCode 的提交记录和讨论区里看到过几类典型错误，这里集中列出来，免得你再踩一遍。
第一类：排序后没有处理重复元素。有人排完序以后，直接用相邻元素差值判断是否连续，但忽略了数组里有重复值的情况。[0, 0, 1, 2]排完序后相邻差值为 0、1、1，如果不做prev == cur去重，会得到错误结果。等到提交发现 Wrong Answer 再去补这个判断，白白浪费一次提交。
第二类：遍历原始数组而不是HashSet，并且没有去重。就像 2.3 节说的，结果不一定错，但会多做很多无用扫描。特定用例下（比如数组只有几个不同值但重复很多次），执行时间会明显变长，甚至超时。
第三类：内层 while 没有用set.contains而是用了类似list.contains的操作。有些同学第一反应是 ArrayList，contains是 O(n) 线性查找。一旦用上，整个算法立刻变成 O(n²)，数据一大就超时。这属于基础 API 复杂度不熟悉的问题。
第四类：递归写法。有人试图用递归或栈去“展开”连续链，比如对每个数递归寻找相邻数。这个过程如果不加记忆化，每个节点会被重复展开多次，复杂度很容易爆炸。能用迭代解决的算法题，优先用迭代。
4.3 几种语言的实现注意事项
如果你用 Java，要注意HashSet的泛型类型。LeetCode 的方法签名是int[] nums，直接迭代即可。使用new HashSet<>()时最好初始化容量，比如new HashSet<>(nums.length * 2)，可以减少扩容带来的性能损耗，不过 LeetCode 上这个差异不大。C++ 选手用unordered_set<int>，注意count()和find()的用法；Python 直接用set()，注意num - 1 not in num_set的写法就是 O(1) 平均时间。每个语言的 API 细节略有不同，但核心算法结构完全一样。
还有一个跨语言的细节：不要用“数组元素做下标”的数组替代哈希表。比如有些题解为了追求常数更小，会做一个“坐标压缩”然后把值映射到数组索引，这个做法本身没问题，但要考虑负数、超大值和稀疏数据，处理起来比用HashSet麻烦得多。作为标准解法，HashSet已经足够好，优化也轮不到这里。
5. 面试加分项：如何向面试官论证，以及与变体的对比
5.1 面试时的复杂度论证话术
面试遇到这道题，常见的对话流程是你先说出哈希表思路，然后面试官追问“你凭什么说这个解法是 O(n)？”很多人在这一步卡住，因为脑子里想的是“反正题解都说是 O(n)”，但没法讲清楚。
我建议用下面这套话术，简洁又有说服力：
先说一句总纲：“我先把所有元素放进 HashSet，去重的同时获得 O(1) 的查找能力。然后我遍历这个集合，对于每个元素，只在它没有前驱（也就是num - 1不存在）时，才向后统计连续长度。”
然后解释复杂度：“每个连续序列只会被它的起点统计一次，而所有连续序列的长度加起来不会超过 n，所以 while 循环的总执行次数是 O(n)。外层 for 循环对每个元素做一次 O(1) 的 contains 判断，也是 O(n)。因此整体 O(n)，没有嵌套复杂度。”
再补充空间复杂度：“我用了一个 HashSet，最坏情况下每个元素都不同，所以空间 O(n)。”
这套回答把“问题的规模”和“操作的次数”对应起来，面试官基本上不会再追问。如果面试官继续深挖哈希查找在最坏情况下可能退化为 O(n)（Java 8 之后链表转红黑树，最坏 O(log n)），你可以回答工程上哈希分布通常均匀、LeetCode 环境默认按平均情况分析，这也是面试中的标准口径。
5.2 并查集与排序方案对比
如果你在面试里遇到“还有别的解法吗”这个问题，有准备的人可以提两个替代方案：并查集和排序。
并查集思路是这样的：把每个数字看成一个节点，如果num + 1存在，就把num和num + 1union 起来，最后统计每个连通分量的大小。时间复杂度 O(n·α(n))，其中 α 是反阿克曼函数，增长极其缓慢，可以近似认为是常数。它的优点是“在线”维护，但代码量和思维量都比哈希表方案大得多。正常刷题，哈希表方案已经足够，并查集可以作为知识储备提一下。
排序方案复杂度 O(n log n)，不满足题目要求，但在真实工程场景里它往往是更好的选择：不用额外空间或少用空间，代码可读性高，而且n不大时排序的常数小，实际跑起来可能不比哈希表慢。面试时主动提这个对比，能体现你不只是背了题解，而是真的理解复杂度在实践中的意义。
5.3 后续扩展：内存受限时如何处理
哈希表方案的硬伤是空间 O(n)。假设输入是一个排好序的、存在磁盘上的大文件，内存装不下全部数据，这时候哈希表方案就不可行了。你能做的选择是：
- 如果数据是流式输入且可以多次读取，可以用外部排序加一次线性扫描，空间占用小，但时间 O(n log n)。
- 如果数字范围很小（比如都是 0 到 10^5 之间的整数），可以用布尔数组、位图等紧凑结构替代 HashSet，把空间压缩到 O(range / 8)。
- 如果允许丢失精度，可以采样估计，但那属于近似算法范畴，和 LeetCode 精确答案的要求不是一个路子了。
这些扩展一般面试不会问，但闲聊阶段主动聊到，能给面试官留下“这人不只会做题”的印象。
6. 刷题之外的几点体会
这道题对我的启发挺大的。技术上它其实不复杂，核心就一个“不要从每个元素都发起扫描，只从起点发起”。但真正想通这个“起点”的价值，需要你对复杂度分析有直觉：双重循环的结构不一定就是 O(n²)，要看内层循环的总访问次数有没有上界。
我在实际面试模拟中见过不少候选人，思路讲得很顺，但一被追问“为什么 while 嵌套在 for 里还是 O(n)”就语塞。建议你准备这道题的时候，不只是把代码背下来，而是能在一个空白的编辑器里，从题意开始推导：为什么要用 HashSet？为什么起点判断能省时间？最坏情况是什么？三个问题都答得上来，这道题才算真正吃透。
最后分享一个小技巧：刷这类“复杂度敏感”的题目，可以顺便整理一个自己的“反直觉清单”。比如“双重循环不一定是 O(n²)”“看似 O(1) 的操作可能因为 API 选错变成 O(n)”“哈希表查询平均 O(1) 但最坏可能退化”。这些认知会在你做系统设计、写业务代码时反过来帮到你。LeetCode 128 只是一个开始，它背后的复杂度思维方式，才是你真正值得带走的东西。
