LeetCode 128 这道题在“最长连续序列”这个小众赛道里属于那种看起来人畜无害、一上手就让人怀疑人生的类型。题目一句话就能讲清楚给你一个无序整数数组找出数字连续的最长序列的长度而且要求时间复杂度 O(n)。第一眼很多人会想最长连续排个序扫一遍不就行了但如果你真这么答面试官多半会追问一句排序是 O(n log n)你凭什么说满足 O(n)如果你还反应不过来那这道题就大概率要翻车了。这道题是 LeetCode 热门 100 题里的常客也是我刷题指南中一直建议反复啃的“思维转换题”。因为它的难点不在代码量而在于你能不能跳出“先排序再统计”的惯性思路理解哈希集合去重后“只从区间起点出发”的线性扫描逻辑。本文我会把这个思路的来龙去脉、代码实现、复杂度证明、易错细节一次讲清楚顺便聊聊面试时怎么把这个题讲出彩。1. 题目拆解与暴力解法的困局1.1 到底要我们求什么先把这个题翻译成人话。给定一个未排序整数数组找出数字连续的最长序列的长度并且要求这些数在原数组里不需要相邻。比如[100,4,200,1,3,2]最长的是[1,2,3,4]长度为 4。注意100和200是孤立的数字没法构成连续段所以它们各自的“连续长度”就是 1。这里有个特别容易踩的坑题目说的是“数字连续”不是“数组下标连续”。很多新手看到“连续”两个字就直接联想到 LeetCode 674 那道“最长连续递增子序列”然后开始在原数组里找相邻位置上的连续递增段。这就完全跑偏了。674 要求子序列在原数组中必须连续且递增128 则完全不关心数字在数组里排在哪、相不相邻只看数值本身能不能串成连续的一段。把这两个题的区别想清楚你就已经绕开了第一个常见的理解误区。还有一个隐藏条件容易被忽略数组可能包含重复元素。比如[1,2,2,3,4]最长连续序列的长度是 4也就是[1,2,3,4]而不是 5。重复的那个 2 不能算两次。所以在任何方案里第一步几乎都是去重否则后面统计长度时一定会被重复值干扰。1.2 为什么排序和暴力都过不了 O(n) 这道坎先说排序解法。把数组排好序然后一次遍历统计连续段的长度遇到不连续就重新计数。这个思路非常自然代码也简单时间复杂度是 O(n log n)空间复杂度如果原地排序就是 O(1)。在绝大多数题目里这种解法已经足够好用了但 LC 128 的题眼就卡在 O(n) 上所以排序解法在第一轮就会被淘汰。再来看暴力解法。假设我们不用排序而是枚举数组里的每个数字 x然后不断检查 x1、x2、x3 是否在数组里每找到一个就继续。这里有两个层级的问题第一如果检查“某个数是否在数组里”用线性扫描那复杂度会爆炸到 O(n^3)基本没法看。第二哪怕你优化了查询用 HashSet 把“存在性检查”降到 O(1)如果对每个元素都从它自己开始向后扩张最坏情况下依然会退化成 O(n^2)。举个退化例子输入是[1,2,3,...,n]每个数都在集合里。外层遍历每个数内层从它开始一直数到 n总次数就是 n(n-1)...1约等于 n^2/2。这样的“哈希表优化版暴力”虽然比纯暴力好但离 O(n) 还差得远。所以问题就变成了到底什么时候才需要从某个数开始向后数答案藏在一个很关键的性质里——在一个连续区间内部只有区间的最小值才值得被当作起点。如果数组里有 1、2、3、4那我就只需要从 1 开始数到 4中间的 2、3、4 完全没必要再数一次。只要能把“哪些数不用数”这件事识别出来复杂度就能降到线性。2. 核心思路哈希集合 只从起点出发2.1 从“找起点”这个关键动作说起整体思路可以拆成五步第一步去重把数组里所有数字丢进 HashSet得到一个不重复的集合。第二步遍历集合中的每个数字 x。第三步剪枝如果 x-1 也在集合中说明 x 不是某个连续区间的最小值直接跳过不从它开始扩张。第四步扩张从 x 开始不断检查 x1 在不在集合中在就继续向后数同时累加长度。第五步更新最大长度。用[100,4,200,1,3,2]这个标准示例走一遍。全部放入 set 之后开始遍历遇到 100检查 99 不在 set 里说明 100 是一个区间的起点。向上数 101不在所以这个区间长度就是 1。遇到 4检查 3 在 set 里说明 4 不是起点跳过。遇到 200检查 199 不在起点。向上数 201不在长度 1。遇到 1检查 0 不在起点。向上数 2、3、4、5得到长度 4。遇到 3 和 2它们的前驱都在 set 里都跳过。最终答案是 4。整个流程里if (!set.contains(num-1))就是那个最核心的剪枝条件。一个数字如果它前面的数字存在它就没有资格当“火车头”只有确认自己是车头才出发向后数后面的车厢全部被跳过。这就是整个算法能跑到 O(n) 的机制所在。这个思路我在实际刷题时有一个很深的体会很多线性算法不是“每个操作都是 O(1)”这么简单而是“每个元素最多被处理常数次”。一旦你接受这个视角很多看似不可能的 O(n) 题都会有突破口。2.2 为什么这个算法是 O(n)摊还证明这可能是面试里最容易被追问的点。很多人代码写对了但一问复杂度就只会背结论说“因为只有起点才会进入 while”这其实不够严谨。我习惯用一个更严谨的说法来证明。内层 while 循环的总执行次数不会超过集合中元素的总数。为什么因为内层循环只在某个元素是连续区间的起点时被触发而一旦某个元素被内层循环的 current 指针访问过也就是作为 x1、x2 被检查到并且 current 走到了它那么后续外层循环再遇到它时它一定有一个前驱。这个前驱就是当前连续区间里排在它前面的那个数。既然前驱存在它就不会再作为起点触发新的 while。换句话说外层循环负责“判断是否存在前驱”每个元素判断一次O(n)。内层循环负责“向后扩张”每次扩张访问到的新元素之后都不可能再被另一个区间访问所以累计也是 O(n)。两者相加整体 O(n)。空间上我们用一个 HashSet 存储全部元素所以空间复杂度是 O(n)。如果你对“最坏情况”还不放心那就拿最极端的输入来试。比如[1,2,3,...,n]除了 1 之外的所有数都有前驱全部被跳过只有 1 作为起点内层从 1 数到 n只执行 n 次。比如全是重复元素的[1,1,1,1,1]set 里只剩一个 1内层只数一次就结束。比如所有元素互相都不相邻的[1,3,5,7,...]每个数都是起点但每个都数不到第二个数内层总次数等于元素个数。无论怎么设计输入总执行次数都保持线性。这里我还想补充一个很多人容易忽略的边界问题如果数组里存在Integer.MAX_VALUE在 Java 中currentNum 1会溢出成负数。一旦溢出set.contains(currentNum 1)就会拿一个负数去集合里找可能导致死循环或者结果错误。稳妥的处理方式有两种一是把 currentNum 声明成 long二是 while 判断时先检查if (currentNum Integer.MAX_VALUE)再 break。细节虽小但能在你没准备的情况下被面试官戳中时很加分。3. 代码实现与复杂度分析3.1 Java 参考实现逐行解读直接上代码这是我刷题时最终沉淀下来的版本class Solution { public int longestConsecutive(int[] nums) { SetInteger set new HashSet(); for (int num : nums) { set.add(num); } int best 0; for (int num : set) { // 如果 num - 1 存在说明 num 不是连续区间的起点跳过 if (!set.contains(num - 1)) { int currentNum num; int currentLen 1; while (set.contains(currentNum 1)) { currentNum; currentLen; } best Math.max(best, currentLen); } } return best; } }这段代码有几个细节值得展开说。第一外层循环遍历的是set不是原始数组nums。为什么因为set已经去重如果遍历原始数组遇到重复数据时虽然不影响最终结果但会产生多余的判断遍历set语义更干净也让复杂度分析更直观。第二currentLen从 1 开始计数因为起点本身就算一个数。第三while循环里每找到下一个数就currentNum这个自增不是写起来好玩而是为了让下一次判断找的是下一个连续值。第四best初始化为 0 而不是 1这样才能正确处理空数组返回 0 的情况。这个版本在 LeetCode 上实测运行时间在同类题解里属于前列。代码量不大真正的难点在于前面思路的推导代码本身反而是最好抄的部分。3.2 Python 版本与一些边界细节Python 版本写法更简洁但也会暴露出一些语言特性上的差异class Solution: def longestConsecutive(self, nums: List[int]) - int: num_set set(nums) best 0 for num in num_set: if num - 1 not in num_set: current num length 1 while current 1 in num_set: current 1 length 1 best max(best, length) return bestPython 里因为整数没有固定位数限制current 1不会出现 Java 那种Integer.MAX_VALUE溢出的问题所以边界处理上会省心一点。但仍要注意如果数组为空best为 0这也是正确结果。set(nums)一行就完成了去重这是 Python 写这类题的优势。这里顺便提一下很多人会犯的一个错误把外层循环写成for num in nums而不是for num in num_set。在 Python 里如果原始数组有大量重复元素遍历原始数组会让外层循环做很多无意义的重复判断虽然结果一般还是对的但代码的“线性”气质就被破坏了。更重要的是面试中讲解思路时用“遍历去重后的集合”来表述逻辑上更自洽你先证明集合里每个元素最多被访问常数次再推导出 O(n)。3.3 复杂度对照表为了方便对比我把几种常见解法整理成一个表格面试时可以直接拿来讲解法时间复杂度空间复杂度是否满足 O(n)核心瓶颈排序后一次遍历O(n log n)O(1)否排序本身的复杂度纯暴力枚举 线性查找O(n^3)O(1)否存在性检查昂贵暴力枚举 HashSet 优化O(n^2)O(n)否每个元素都盲目扩张并查集O(n α(n))O(n)接近实现复杂常数额大哈希集合 起点剪枝O(n)O(n)是无从表里能看出来哈希集合 起点剪枝这个方案在复杂度上确实是唯一严格满足 O(n) 的实现。并查集虽然理论复杂度也接近线性但实现复杂度高、常数大在面试中通常不是最优解。4. 常见问题、变体与面试扩展4.1 常见误区与排查记录我在实际刷题和给同事讲题的过程中总结出几个高频问题统一整理成速查表症状可能原因解决方案代码超时缺少if (!set.contains(num-1))剪枝加上剪枝只从区间起点扩张结果比预期长没有处理重复元素遍历去重后的 set而不是原数组结果比预期短误把原数组下标连续性当成数值连续性来统计回到题目定义只关注数值是否连续死循环或无限增长currentNum 1溢出用 long或在边界处 break空数组返回 1best初始值设置错误best初始化为 0逐个解释一下。第一个问题最常见很多人代码写完后发现超时就是忘了剪枝导致每个元素都成为起点复杂度退化成 O(n^2)。第二个问题的场景一般是数组里有大量重复值比如[1,1,2,2,3,3]如果遍历原数组并且计数逻辑写得不严谨会把重复值重复计入得出一个偏大的长度。第三个问题是理解层面的建议重新去看 LeetCode 674 做对比。第四个和第五个则是边界条件属于老手也会偶尔踩的坑。我还遇到过一个比较隐蔽的情况有人把 while 循环写成了while (set.contains(num currentLen))然后在循环体里只currentLen。这种写法在逻辑上等价但需要格外小心 currentLen 的增长时机。如果先判断再自增的顺序写反长度就会少 1。我的建议是统一用currentNum指针 单独currentLen计数的写法看起来多一个变量但不容易出错。4.2 相关变体题与扩展思路LC 128 的解法思路很经典所以它衍生出不少变体题面试时如果能把它们串起来讲会让面试官觉得你有体系化的理解。第一个是 LeetCode 674最长连续递增序列。它要求子序列在原数组中连续且递增因为下标必须连续所以一次遍历就能解决。这里“连续”指下标连续和 128 的“数值连续”恰好形成对比。第二个是二叉树的版本比如 LeetCode 298 和 549分别求单路径和双路径的最长连续序列。这类题需要把“连续序列”的判断从数组搬到树上处理逻辑更复杂但核心还是“从某个点出发沿着值递增的方向延伸”。第三个是并查集的解法把每个数字和自己相邻值x-1、x1能连则连最后统计每个连通分量的大小。这个思路能解决但实现成本偏高我一般用来做复杂度对比而不是首选方案。第四个是哈希表动态规划的写法用 map 记录以某个数为结尾或开头的最长连续长度插入新数时检查x-1和x1的已有长度动态更新区间两端点的值。这个解法的好处是可以处理在线查询场景属于更进阶的扩展。我个人比较推荐把哈希表动态规划这版作为进阶理解材料它能让“区间长度怎么维护”变得可视化也能帮你面试时多一条思路给自己留出更多周旋空间。4.3 面试中如何把这道题讲出彩这道题是很好的“思维展示题”代码量小但考察点很密集。面试时我最推荐的答题顺序是这样的先一句话点破为什么排序不行题目要求 O(n)排序的第一步就是 O(n log n)所以必须换思路。接着讲去重先放进 HashSet把重复值消掉后面统计长度才不会被干扰。然后引出关键观察一个连续区间里只有最小的数字才有资格作为起点判断方法就是看x-1是否存在。再讲实现和复杂度每个元素最多被外层判断一次、被内层扩张访问一次整体 O(n)空间 O(n)。最后一定要补边界条件空数组返回 0重复元素不影响结果Integer.MAX_VALUE溢出问题。这个顺序的好处是它符合“问题定义 - 思路推导 - 关键剪枝 - 复杂度证明 - 边界防范”的完整链条。每讲一步面试官都能看到你的思考过程。如果你时间充裕还可以主动提一句“如果允许 O(n log n)排序后再扫描会更简洁但既然题目卡了复杂度所以用这套哈希集合方案。”这种对比能体现你对不同复杂度方案的取舍能力。根据我个人经验这题在面试中的定位更像“谈心题”它不像动态规划那样背模板也不像图论那样考硬知识它考的就是你能不能在压力下切换思考角度。如果能把这个思考过程完整地展现出来往往比直接给出正确答案更让面试官满意。最后再分享一个我自己的刷题心得。遇到“要求 O(n)”的题目先不要急着写代码先问自己一句话有没有哪个元素是根本不需要被处理的LC 128 的答案是有区间内部的所有元素都不需要单独处理。一旦你找到“谁可以被忽略”线性解法往往就浮出水面了。这个思路我后来在不少看似复杂的题里都用上了算是刷题生涯里很值的一次积累。