LeetCode 128这道“最长连续数列”我刷了三遍才算真正吃透。不是因为题目多难而是第一遍我用的是“排序后扫描”的偷懒解法第二遍背了哈希表的答案却讲不清为什么能 O(n)直到第三遍才摸清楚这道题考的不是“你会不会写循环”而是你懂不懂“用空间换时间”什么时候换、怎么换才划算。作为 LeetCode 热门 100 题里的常客它在面试中出现频率极高而且经常被拿来当“哈希表思想”的入场题。这篇文章我把自己踩过的坑、最终沉淀下来的解法思路、以及监修过不少同学代码后总结的易错点一次说清楚。1. 理解题意连续不是子序列先分清概念1.1 题目到底在问什么题目给你一个未排序的整数数组要你找出数字连续的最长序列的长度。注意这里说的是“序列”而不是“子数组”意味着你不需要关心元素在数组里的原始位置只需要关心这个集合里能不能凑出x, x1, x2, ...这样一串连续递增的整数。举个我自己早期理解错的例子[100, 4, 200, 1, 3, 2]正确答案是 4因为 1、2、3、4 可以连成一段长度为 4 的连续序列。而我第一次做的时候以为是找数组中连续出现的子串试图在数组里滑动窗口找相邻位置上的连续值结果绕了好大一圈。核心就一句话把数组看成集合而不是看成有顺序的列表。这一点想通了后面所有解法都会自然浮现。数组里元素出现的位置毫无意义唯一有意义的是“这个值存不存在”。1.2 几个边界例子帮你校准思路我建议你先在心里跑一遍这几个用例再去看任何题解输入数组期望输出为什么[]0空数组没有元素没有序列[1]1单个元素本身构成连续序列[1, 2, 0, 1]3虽然 1 出现了两次但 0、1、2 连续长度才是关键[9, 1, 8, 2, 7, 3]3没有 0 或 4 这种“桥梁”最长也只是 1、2、3 或 7、8、9[10, 11, 12, 13, 14, 1, 2]5最长段是 10 到 14而不是 1、2 这种小段我最开始拿到[1, 2, 0, 1]时错误地认为需要把重复的 1 处理成“也能贡献长度”事实上重复项在集合思维下根本不需要特殊处理Set 自动去重。2. 从暴力到进阶为什么 O(n) 是这道题的门槛2.1 最容易想到的排序解法为什么会被追问排序解法实在太直觉了排完序以后数组变成从小到大有序排列只要后一个数比前一个数大 1就算连续段加长如果相等就跳过否则重新计数。代码二十行不到逻辑一目了然。def longestConsecutive(nums): if not nums: return 0 nums.sort() ans 1 cur 1 for i in range(1, len(nums)): if nums[i] nums[i - 1]: continue if nums[i] nums[i - 1] 1: cur 1 else: cur 1 ans max(ans, cur) return ans这段代码本身没有错所有普通用例都能过。但面试官一定会追问时间复杂度是多少你说 O(n log n)。他再问能不能 O(n)如果你答不上来这道题基本就降了一个档次。我后来在工作中回想这件事发现排序解法其实代表了一种思维惯性面对乱序数据先把它变有序再处理。这种思路在很多业务脚本里完全够用LeetCode 这题故意设了硬门槛就是要逼你摆脱这个惯性。2.2 哈希表的核心查找成本近似 O(1)不排序我们还能怎么知道x1存不存在答案是把所有数字放进哈希表然后针对每个数字在表里向“右”探测。哈希表的优势在于判断一个数是否存在于集合中平均时间复杂度是 O(1)。你要探测x1存在吗查一次哈希表。x2存在吗再查一次。看起来像是双重循环为什么整体还能是 O(n)关键就在于不是每个元素都需要从头向外探测。如果你对每个元素不管三七二十一都往右数一遍最坏情况[1, 2, 3, 4, 5]第一个元素数 5 次第二个数 4 次……整体 O(n²)哈希表救不了你。真正的优化在于只从每个连续段的“起点”开始数。一个段只有一个起点所有数字加起来只会被数一次总时间复杂度自然回到 O(n)。3. 核心实现哈希表去重与起点判定3.1 选对容器HashSet 还是 HashMap很多初学者会纠结是不是要用 HashMap 记录每个数字所在的段长度其实这题最标准的解法一个 HashSet 就够了。之所以用 Set 而不是 Map是因为我们只关心“存在性”。你不需要知道x对应哪一段、也不需要更新段头段尾的长度那是另一道经典题“连续区间合并”的做法。这题你只需要快速回答两个问题数字x在不在数组里数字x-1在不在数组里如果x在但x-1不在说明x是一段连续序列的起点。如果x-1也在说明x不是起点它已经属于以某个更小数字开头的段没有资格开启新计数。这个“只看起点”的设计是整个算法的灵魂。我见过不少同学用 HashMap 硬写也能过但代码会变长而且容易在处理更新逻辑时出 bug。能用 Set 解决的不要给自己加戏。3.2 起点判定的妙处判断起点这一步可能看起来多了一个哈希查找但它恰恰是把复杂度从 O(n²) 降回 O(n) 的原因。想象数组[1, 2, 3, 4]遍历到 1检查0在不在集合里。不在所以 1 是起点往上数 2、3、4得到长度 4。遍历到 2检查1在不在集合里。在所以 2 不是起点直接跳过不往上数。遍历到 3、4 同理全部跳过。每一个连续段只会从起点被扫一次段内其他元素进入循环时发现x-1存在马上跳过。整体来看每个元素最多被“向后数”一次均摊 O(n)。3.3 完整代码与逐段拆解我用 Python 写一版最干净的实现def longestConsecutive(nums): num_set set(nums) max_len 0 for x in num_set: if x - 1 not in num_set: cur x cur_len 1 while cur 1 in num_set: cur 1 cur_len 1 max_len max(max_len, cur_len) return max_len逐段拆解第一步去重建集合。set(nums)把数组变成集合这一步自动处理重复值。max_len记录全局最长长度初始为 0这样空数组也能正确处理。第二步遍历集合中的每个数字。注意是遍历集合而不是原数组两者在去重后等价但遍历集合能避免重复元素带来的重复计算。if x - 1 not in num_set这个条件就是“起点判定”。它的意思是如果比 x 小 1 的数字不存在说明 x 没有前驱它只能是一段连续序列的开头。第三步从起点向大数方向延伸。while cur 1 in num_set不断把cur加 1每加一次cur_len加 1。这个 while 循环虽然看起来是嵌套的但因为起点判定的存在内层循环的总执行次数等于所有连续段的总长度而每个数字只属于一个段所以总次数不超过 n。max_len max(max_len, cur_len)更新答案。C 版本几乎一样的思路用unordered_setint longestConsecutive(vectorint nums) { unordered_setint numSet(nums.begin(), nums.end()); int maxLen 0; for (int x : numSet) { if (!numSet.count(x - 1)) { int cur x; int curLen 1; while (numSet.count(cur 1)) { cur; curLen; } maxLen max(maxLen, curLen); } } return maxLen; }Java 版本class Solution { public int longestConsecutive(int[] nums) { SetInteger numSet new HashSet(); for (int num : nums) numSet.add(num); int maxLen 0; for (int x : numSet) { if (!numSet.contains(x - 1)) { int cur x; int curLen 1; while (numSet.contains(cur 1)) { cur; curLen; } maxLen Math.max(maxLen, curLen); } } return maxLen; } }三种语言逻辑完全等价你工作中用哪个顺手就用哪个练。我面试时习惯写 Python因为代码量少能把更多时间花在讲思路上。3.4 为什么跳过起点能避免超时这里再深入一层。有人会问如果我只判断“x-1 不在集合中才作为起点”会不会漏掉某些不是最左端、但也能构成最长段的情况不会。因为任何连续段[a, a1, ..., b]它的最左端一定是a而a-1一定不在集合中否则a就不是最左端段可以往左扩展。所以每个段都会且仅会被它的最左端触发计数。反过来如果你不做起点判断对每个元素都向右扩展最坏情况下[1, 2, 3, ..., n]这组数据会让你对每个元素都做一次 O(n) 的探测总复杂度 O(n²)。LeetCode 的隐藏测试用例一定会覆盖这种极端情况那时候你就能体会到超时的滋味。我第一遍写暴力解法时就在[0, 1, 2, ... , 99999]这类用例上超时当时还以为是哈希表不够快后来才明白是算法结构问题。4. 刷题路上的坑重复元素与边界问题4.1 重复元素不是小问题数组[1, 2, 0, 1]这样的输入如果你用的是“排序后扫描”方案必须单独处理“等于前一个数”的情况忘记的话会把长度算错。如果你直接用原数组遍历而不去重1出现两次会让你的起点判定产生混乱第一次看到 10不存在于是从 1 往后数到 2长度 3第二次又看到 1又是起点又数一遍。结果没错但白白多算了一次如果后续数据规模大了这种重复计算消耗很可观。用set(nums)后重复元素直接消失问题自然解决。我建议你无论用哪种语言第一步都是立刻把数组转成集合不要留到后面再处理。4.2 空数组与单元素边界空数组返回 0。max_len初始化为 0 就能覆盖这种情况但前提是你不要在循环外把max_len初始化成 1。我见过不少代码写成max_len 1 for x in num_set: ...然后空数组进来直接返回 1这是错的。正确做法是把初始值设为 0或者单独判断空数组。单元素数组[5]返回 1。这个用例用来验证你的起点判断和长度累加逻辑是否正常5 的左边没有 4它是起点进入 while 后 6 不在集合cur_len保持 1返回 1一切正常。4.3 最大长度的统计时机长度更新要放在每个起点段计算完以后不要放在 while 循环内部每加一次就更新一次。虽然两种写法结果相同但放在外部逻辑更清晰一个段算完了再决定它是不是全局最大。放在内部会多出无意义的比较操作代码也容易让人误解。还有一点遍历集合时如果你在 while 循环里改了集合内容比如删除已访问元素会直接报错或导致未知行为。我早期想优化成“访问过就删”Python 里for x in num_set时执行num_set.remove(x)会抛出RuntimeError: Set changed size during iteration。要边遍历边删除只能改用while num_set弹出一个元素再处理但那样代码会复杂很多。实测下来不删元素的解法已经足够快LeetCode 128 的所有测试用例跑完一般只要几十毫秒。5. 一题多解并查集思路与面试演进5.1 并查集怎么套进来这道题除了哈希表用并查集也能解而且思路非常优雅把每个连续的数字合并到同一个集合中最后统计每个集合的大小。并查集的核心思想是每个数字都指向自己的“根”连续的数字通过union(x, x1)合并到一起。初始时每个数字单独成集合大小都是 1遇到x和x1同时存在就合并合并时记录集合大小最后扫描所有数字找出最大的集合大小。很多同学觉得并查集难其实把它理解成“给数字分组”就行。比如[100, 4, 200, 1, 3, 2]一开始 6 个数字各自成组。遍历时发现 1 和 2 同时在合并2 和 3 在合并3 和 4 在合并。最终 1、2、3、4 变成一个组大小 4。100 和 200 仍然是单独的组答案取最大组大小 4。并查集写法比哈希表长但它考察的是另一种数据结构掌握程度。如果你在面试中已经写了哈希表解法可以主动提一句“这题还能用并查集做”面试官往往会眼前一亮顺着问你并查集的实现细节。这时候你需要能流畅写出find和union并且解释路径压缩和按秩合并的优化。5.2 哈希表之外的改进方向还有一种思路是“区间扩展”用两个哈希表分别记录每个连续区间的左右端点长度核心逻辑是当你插入一个新数字时检查它左边和右边的数字是否已经在某些区间里然后把新区间的长度更新到新端点。这个方法在处理“区间合并”类问题比如力扣 57 插入区间、力扣 352 数据流中的区间时很有用但放在这题里属于“高射炮打蚊子”代码长度和心智负担都远超标准解法。我认为学习这道题的正确路径是先能写出排序解法能讲清楚复杂度。再掌握哈希表 起点判定能写能讲为什么 O(n)。有余力再看并查集作为知识扩展。区间合并法了解即可不必深究。5.3 与相关题目的横向对比你在刷 LeetCode 时一定会遇到跟 128 同类型或者容易被混在一起的题。这里我列几个我实际刷过、并且觉得有对比价值的题目核心思路与 128 的差异力扣 994 腐烂的橘子BFS 多源扩散关心“传播时间”依赖二维网格需要队列逐层处理力扣 073 爱吃香蕉的狒狒二分查找在“速度范围”里做二分与连续集合无关力扣 1 两数之和HashMap 存补数同一个哈希表思路但只查一次匹配力扣 674 最长连续递增序列一次遍历动态规划要求在原数组中连续不允许跳过位置把 128 和 994 放一起对比特别有意思腐烂的橘子用 BFS 是因为腐烂过程从多个源头同时扩散需要队列记录层数最长连续数列用哈希表是因为你只需要判断存在性不需要“扩散路径”。两者都是“围绕一个核心数据结构做扩展”但方向完全不同。我建议刷题时用这种对比方式复习比单纯刷数量有效得多。6. 我的实际刷题心得与建议6.1 从这道题学到的最重要思维我刷了这么多题128 是我心目中“哈希表思想”的最佳教学题。它教会我一件事当数据本身无序而你要判断的是存在性与连续性时第一个念头应该是哈希表而不是排序。排序在很多场景下是万能的但它的 O(n log n) 成本在某些题目里就是过不去。你能不能在关键时刻放弃“万能解法”选择更巧妙的路线这是面试官真正想观察的。另一个让我印象深刻的点是“只从起点开始计数”的思维方式。这本质上是一种“减少重复计算”的优化策略。你不需要对每个元素都跑完整条链你只需要找到链的起点。类似的想法在力扣 200 岛屿数量里也有体现你只需要在遇到新岛屿时 DFS被访问过的格子直接跳过整体复杂度才能保证线性。6.2 相关题目练习路线如果你刚刷完 128我建议接着刷这几题巩固同类思想力扣 1 两数之和最简单的 HashMap 应用用来建立“用哈希表查存在性”的条件反射。力扣 202 快乐数用 Set 检测循环体会“集合去重”的另一种应用。力扣 349 两个数组的交集Set 的集合操作难度低适合找手感。力扣 217 存在重复元素直接考 Set 去重一分钟能写完的那种但能帮你巩固基础。力扣 674 最长连续递增序列同样是连续序列但必须在原数组连续位置用来对照 128 理解题目限制条件的差异。这五道题整体难度偏低但能帮你把哈希表、集合、连续序列这几个关键词串成一张知识网。等这些都写顺手了再回头用并查集重新解一遍 128你会发现自己对数据结构的理解又深了一层。我个人在实际操作中的体会是LeetCode 128 不存在“看一眼就会”的捷径它考察的是你在混乱数据中提炼结构的能力。多写几遍、多讲几遍、多对比几道相关题这笔时间花得绝对值得。