LeetCode Hot100刷到第3题128.最长连续序列。这题在题库里属于那种“题干短、限制狠、解法一眼看上去有点反直觉”的题目给你一个未排序的整数数组让你找出数字连续的最长序列长度而且时间复杂度要求是O(n)。很多人第一次看到这个限制第一反应是排序然后陷入沉思——因为排序本身就是O(nlogn)。这题的经典解法是用哈希表加一个“只从起点开始扩散”的小技巧把查找连续段的代价摊到每个元素恰好一次。如果你正在刷Hot100准备面试或者想理解“怎么用O(1)查找换取O(n)整体复杂度”这类空间换时间的套路这道题值得停下来多想想。我前两遍刷的时候代码能跑通但心里总觉得不踏实第三遍把复杂度证明和边界情况捋清楚之后才真正敢在面试里写这个解法。1. 题面只有“未排序”三个字但O(n)限制把所有常规思路都堵死了1.1 先定位这是什么题最长连续序列在Hot100里排得很靠前因为它是哈希表专题的代表题。题干一句话给定一个未排序的整数数组nums找出数字连续的最长序列的长度。题目同时要求时间复杂度为O(n)。这里的“连续序列”不是“数组中位置连续的子数组”而是“数值之间相差1的一串数字”。比如nums [100,4,200,1,3,2]答案不是[1,3,2]这种按原顺序截出来的东西而是从1到4这一段长度是4。因为数组本身可以重排1、2、3、4凑在一起就是一个完整的连续段所以题目说的“连续”只关心值不关心下标位置。这一点如果一开始没想清楚后面所有思路都容易跑偏。再看两个边界例子nums [0,3,7,2,5,8,4,6,0,1]这个数组里包含了0到8的所有整数虽然原顺序非常乱但最长连续序列就是0到8长度9。nums []空数组没有元素结果应该是0。这些例子都在题目描述里出现过但很多人只盯着官方示例看忽略了空数组和重复元素这些关键边界。1.2 为什么排序被一票否决看到“最长连续”最自然的想法是排序后遍历数组排好序之后连续段自然就挨在一起了遇到nums[i] nums[i-1] 1就累加否则重置。这个思路很干净但排序本身是O(nlogn)题目要求O(n)所以这条捷径直接堵死。这里有个很重要的“题感”当一道算法题明确要求O(n)时间而你又需要反复判断“某个数是否存在、某个数的下一个邻居是否存在”时能依赖的基本只有哈希表。哈希表的contains操作是O(1)查一次很快查n次也就是O(n)。题目没有限制空间复杂度所以这是一种典型的空间换时间思路空间O(n)完全可以接受。1.3 读懂题目后还要注意什么除了未排序和O(n)这题还有两个隐性信息容易被忽略。第一个是数组里可能有重复数字比如刚才的[0,3,7,2,5,8,4,6,0,1]里出现了两个0。连续序列关心的是“有没有数字3”而不是“3出现了几次”所以重复值对结果长度没有贡献但它会影响实现效率。第二个是值域可能包含负数。比如nums [-1,0,1,2]最长连续序列是-1到2长度4。负数在这个解法里完全不是问题哈希表不关心你是正是负只关心key在不在。这两个信息合在一起才会导向“用Set先全部存起来再去重处理”的方案。2. 先别直接写Set解法看看暴力循环到底浪费了什么2.1 两层循环的暴力解法长什么样最直观的暴力法是把数组所有元素放进一个Set然后外层遍历每个元素内层用一个while不断向右找“当前值1”是否存在。伪代码大致是set 所有元素 for num in 数组: cur num length 1 while cur 1 in set: cur 1 length 1 ans max(ans, length)这个思路和最终解法已经很接近了但复杂度不对。假设数组是[1,2,3,4,5]第一次从1开始能一路找到5得到长度5第二次从2开始又一路找到5长度4第三次从3开始再来一遍。每一轮都从头扫到尾总共做了大约O(n²)次查找。哪怕每次contains都是O(1)整体也会在数据量大时超时。2.2 重复计算来自“非起点也在扩展”仔细看上面对[1,2,3,4,5]的暴力过程会发现一个关键问题从2、3、4、5开始的扫描其实覆盖了从1开始那次扫描已经走过的路。更本质的原因是一个连续段里只有最小的那个元素是真正的“起点”。从1开始往右扫一遍整个段就被完整覆盖了从2开始再扫只是把已经扫过的区域重新扫了一遍属于纯粹浪费。段的长度越大这种浪费越离谱。所以优化的方向就清楚了我们要想办法让每个连续段只从“最左侧起点”开始扫描其他位置全部跳过。想做到这一点就必须能用O(1)时间判断“当前元素是不是起点”。2.3 重复元素会把浪费进一步放大如果直接遍历原始数组而不是去重后的Set还有一个更隐蔽的大坑重复元素会导致同一段连续序列被重复扫描。随便举个例子nums [1,1,1,1,2,3,4]这里有一万个1。如果直接遍历原数组每遇到一个1都会发现“1是起点因为0不存在”然后从1开始一路扫描到4。也就是说这段长度为4的序列会被重复扫描一万次直接变成O(n²)。但如果你先放进Set遍历的是去重后的集合那一万个1在集合里只剩一个1这个问题就自动消失了。理解了这个过程你就会明白为什么很多题解强调“遍历set不是遍历nums”。3. 核心只有一句话只有缺失左邻居的元素才有资格当起点3.1 先把所有数字丢进HashSet第一步很简单把数组里所有元素放进一个HashSet。这一步做了两件事去重以及为后续的O(1)成员判断做铺垫。之后遍历的是Set而不是原数组。因为Set里没有重复值每个不同的数字只会被当作候选起点处理一次。你可能会担心遍历Set得到的顺序是随机的会不会影响结果不会。我们判断的是“某个数是否存在”和遍历顺序没有任何关系。3.2 contains(num - 1)就是“起点过滤”的准则遍历Set里的每个元素num时关键判断来了if set.contains(num - 1): 跳过这个元素不可能是起点 else: 从num开始向右扩散为什么num - 1存在时就可以跳过因为如果num - 1也在数组里那num一定是某个更长连续段的一部分那段序列一定是从左边的某个更小值开始的。从num开始向右扫得到的长度最多是完整段减去左边那一段注定不是最优解。反过来如果num - 1不存在说明num面前没有数字跟它连着它只能是自己所在连续段的最左端点。从它开始向右扩散扫到的长度就是这一整段的完整长度。用一个生活化的类比一条队伍排队只有“排头”才知道整个队伍有多少人你从队伍中间任意一个人开始数永远数不到完整队伍的人数。所以我们要让机制自动识别排头也就是“左边没人接应”的那个人。3.3 用官方示例完整走一遍拿nums [100,4,200,1,3,2]来推演。先构建set {100,4,200,1,3,2}。然后遍历set遇到100检查99是否存在——不存在说明100是起点。接下来看101、102……都不存在所以这一段长度是1。遇到4检查3是否存在——存在所以4不是起点跳过。遇到200检查199是否存在——不存在看201、202……都不存在长度1。遇到1检查0是否存在——不存在说明1是起点。从1往后扫2在长度23在长度34在长度45不在结束。这一段长度是4。遇到3检查2是否存在——存在跳过。遇到2检查1是否存在——存在跳过。最终best max(1,1,4) 4。注意4、3、2都被跳过了但这没有损失因为从它们开始扫到的长度分别是3、2、1都比从1开始的4要短而且如果让它们各自去扫反而会重复遍历2、3、4这些点增加复杂度。3.4 负数、0、空数组和单元素数组都被这套逻辑自动覆盖有人可能会担心边界条件其实这些边界在“起点过滤”逻辑下天然成立不需要额外特判。负数场景nums [-1,0,1,2]。遍历到-1时检查-2是否存在——不存在从-1开始往右扫-1、0、1、2都在长度4。遍历到0时检查-1存在跳过遍历到1时检查0存在跳过。完全没问题。0的场景nums [0,1,2]。遍历0时检查-1是否存在——不存在注意-1和0的关系并不特殊Set里没有-1就是没有-1。然后从0扫到2长度3。空数组Set本身就是空的best保持初始值0返回0。所以代码里best一定要初始化成0不能初始化成1否则空数组就会返回错误答案。单元素数组nums [7]。检查6是否存在——不存在从7往右看8也不存在长度1。返回1正确。4. 我在LeetCode提交通过的版本Java和Python各一份4.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) { if (!set.contains(num - 1)) { int current num; int currentLen 1; while (set.contains(current 1)) { current; currentLen; } best Math.max(best, currentLen); } } return best; } }几个关键写法再啰嗦一遍第一给Set赋值用的是原始数组但遍历时用的是set第二while循环里判断的是current 1然后让current递增这样做一来能保证循环向前推进不会死循环二来配合着currentLen同步增长逻辑很顺第三current之后再用contains判断下一格直到断裂。4.2 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 current_len 1 while current 1 in num_set: current 1 current_len 1 best max(best, current_len) return bestPython的set(nums)一行就把去重做完了。这里有个细节遍历set的过程中绝对不能修改set否则会抛RuntimeError。我们这里只做contains判断不增删元素所以安全。4.3 提交中常见错误对照表我整理了一张表把最常见的错误写法和后果列出来方便你自查。错误写法后果正确做法遍历原数组而不是set重复元素导致同一段被反复扫描最坏O(n²)先构建set再遍历set缺少if起点判断每个元素都向右扩展和暴力法一样O(n²)加上contains(num - 1)过滤while里判断current - 1扫描方向反了逻辑混乱容易死循环或漏算用current 1往右扩散best初始化为1空数组返回1而不是0best初始化为0用List.contains代替Setcontains是O(n)整体复杂度变成O(n²)用HashSet或Python的set5. 为什么它真的只有O(n)一份能说给面试官听的复杂度证明5.1 外层遍历的代价外层循环遍历的是SetSet中不同元素的个数最多等于数组长度n所以外层遍历的消耗是O(n)。每个元素做一次contains(num - 1)判断也是O(1)。这两步加起来已经是O(n)。5.2 内层while的总次数为什么不是O(n²)这是整个复杂度证明最核心的地方也是面试官最喜欢追问的地方。while循环确实会导致每个起点向右扫描一段看着像嵌套循环好像应该是O(n²)。但仔细想while循环只会在“起点元素”处触发而一个起点一旦触发它会顺着自己的连续段向右扫过段内所有元素。举个例子[1,2,3,4,5]这个数组起点1进入while后扫到2、3、4、5所以2、3、4、5这四个值都被“访问过”了。之后遍历到2、3、4、5时它们因为contains(1)、contains(2)、contains(3)、contains(4)为true而被跳过根本不会再次进入while。换句话说每个不同的元素最多只会被一个起点扩散访问一次。所有while循环的迭代次数加起来不可能超过不同元素的个数n。所以外层O(n)内层所有迭代总和也是O(n)整体就是O(n)。你可以把每个连续段想象成一条巡逻路线只有排头会带队走完整条路队里其他人都不需要再走一遍。5.3 空间复杂度HashSet里存储所有不同的数字最坏情况下数组里全是不同元素空间就是O(n)。除了这个Set代码里只用了常数级的额外变量比如current、currentLen、best。所以空间复杂度也是O(n)。题目没有限制额外空间这个方案在LeetCode上是标准解法。5.4 还有哪些替代方案以及为什么不是首选如果不要求O(n)当然可以排序后扫描这是最简单的路子。但这里的核心限制就是时间排序秒出局。并查集可以解这道题思路是把连续相邻的值做union最后找最大的连通块大小。这个方案理论上也能做到接近O(n)但常数很大而且需要为每个值维护一个节点理解和编码都比HashSet方案绕。面试时如果被问到可以说“并查集也能做”然后简单说一下区间合并的直觉但没必要作为主解。位图法只有在值域已知且比较密集的时候才实用比如值只在0到100之间。对普通整数数组来说值域可能极大且包含负数位图会浪费大量空间不做推荐。6. 刷到第三遍才发现的事几个坑和面试官更关心的追问6.1 坑1把“连续序列”当成“连续子数组”这是最大的概念坑。有人拿到题会下意识去找“原数组中位置连续的一段”然后陷入滑动窗口的思维。但这题里的连续纯粹是“数值连续”数组位置没有任何关系。哈希表为什么在这里这么好用就是因为我们只需要判断“某个值存在”完全不需要管它出现在哪个下标。如果不把这个概念扭转过来后面所有解法都理解不了。6.2 坑2遍历原数组而不是set导致隐式超时我第一次写这题时习惯性地写了for (int num : nums)而不是for (int num : set)。结果是[1,1,1,1,2,3,4]这种数组能AC吗小数据量能但数据量一大就超时。原因前面已经说了重复的起点会把同样的扩展过程重复好多遍。就算contains(num - 1)能过滤非起点但对于“自己的前一个值不存在”的那些重复元素每个都会触发一次完整扩展。只有先走进set才能从根源上去掉重复值的影响。6.3 坑3边界与方向细节空数组返回0这个边界靠best初始化来解决。方向问题则是while里应该用current 1不是current - 1。有人想从右往左扫结果逻辑完全反了还可能死循环。记住起点是最左端扩散一定是往右即值递增的方向。6.4 面试追问一如果输入是数据流如何在线维护最长连续段长度这题改成“数字一个一个到达”就不适合上面的整体建Set方案了。面试官想看你能不能把静态解法改成在线解法。常见思路是用两个哈希表维护每个连续段的左右端点来一个新数字x时看看x - 1是否已经在一个段的右端看看x 1是否已经在一个段的左端然后把左右两段和x合并成一个新段记录新段长度。这个思路本质上是区间合并。比如已经有[1,2]和[4,5]这时来一个31到2这段的右边是24到5这段的左边是43夹在中间于是合并成[1,5]长度为5。你可以不用写出完整代码但把这个过程和为什么要维护端点说清楚已经能加分。6.5 面试追问二数字换成负数、Long或大整数代码需要改吗哈希表对负数、Long、大整数完全通用contains判断不关心值的类型只关心对象是否相等。代码层面基本不用改。但有一个隐藏问题如果值接近类型上限比如Long.MAX_VALUE那么current 1可能会溢出。Java的long溢出后会变成负数contains判断就错乱了。如果面试官故意问这个你补一句“需要小心数值上限必要时用减法判断或改用BigInteger”就能体现细节敏感度。6.6 面试追问三它和“最长非降子序列非连续”是同一个套路吗不是。热搜里经常有人把这两个知识点混在一起因为都带“连续”“序列”这些字眼但它们是两个方向的题目。最长连续序列也就是本题只关心值是否相差1、这一段在值域上是否连续不要求数组下标顺序。解法是HashSet加起点扩散O(n)。最长非降子序列也就是常见的LIS变形关心的是在原数组的下标顺序里选一个子序列使得后一个值不小于前一个值允许跳过中间元素。经典解法是动态规划O(n²)进阶可以用贪心加二分做到O(nlogn)。它和哈希表没关系核心在“状态转移”和“二分维护上升栈”。维度最长连续序列本题最长非降子序列LIS连续的含义数值差值为1值非降下标递增是否要求原顺序不要求要求下标递增典型解法HashSet 起点扩散动态规划 / 贪心 二分时间复杂度O(n)O(n²) 或 O(nlogn)面试时如果被追问“你能用类似思路做别的题吗”你可以先说清楚这两个概念的区别再谈扩展这样会让面试官觉得你不是背模板而是真的理解题与题之间的边界。7. 把“找起点再扩散”的观察力用到更多题里7.1 什么情况下可以套用这个套路这套思路的适用场景有一个非常明显的特征数组无序、要判断某个值是否存在、要找一段值域上连续的东西。不管它是整数数组、字符集合还是某种可比较的离散值只要满足“通过O(1)判断邻居是否存在”就大概率可以用“先哈希再找起点再扩散”的方式优化。判断自己有没有抓住精髓可以问一个问题这个场景里什么东西能立刻被识别为“一段的起点”在本体题里起点的特征是“左邻居不存在”。在别的变体里起点可能换成“上一个状态不存在”“前一个字符不存在”等等。7.2 变体一最长连续等差序列如果把“差值为1”改成“差值为某个固定步长d”思路可以平移。比如求最长连续等差数列可以先枚举公差然后对每个公差单独跑一次“找起点再扩散”。起点判断就变成“num - d不在Set里”。这题的复杂度会乘上一个公差枚举数但如果公差范围可控思路完全一致。再延伸一步如果公差不确定需要枚举所有数对来确定公差那就会从这题的O(n)变成O(n²)这也是可以讨论的演进方向。7.3 变体二字符串里出现过的最长连续字母段把哈希表里的整数换成字符本质还是一个起点扩散问题。比如给定一个字符串找出出现过的最长连续字母序列长度。可以先把字符去重存进HashSet遍历字符时判断“这个字母的前一个字母是否存在”如果不存在就按字母序向右扩散。这种变体在面试题里出现频率不算高但一旦出现如果你能把整数版的代码思路平移过去面试官会明显感觉到你是真的掌握了解题模式而不是只会背一道题。7.4 变体三扩散思想与图相连通块的关系“找起点再扩散”的本质其实是把一个集合按某种规则切分成若干个“块”然后找最大的块。这和DFS/BFS找岛屿连通块的思路很像在图里你先找一个未访问的节点作为起点然后通过邻居关系把整个连通块全部访问一遍记录大小再跳到下一个未访问节点。区别只在于图里的邻居是通过边表给的而这道题里的邻居是“当前值1”这个关系。如果你能把这两者联系起来再去看并查集解法就会很通透——并查集就是另一种维护“块”合并的方式和本题的Set思路殊途同归。7.5 我推荐怎么练这道题我的建议分三步。第一步先写一个不带起点过滤的暴力版本感受一下重复计算发生在哪里。第二步加一个起点过滤改成最终版本跑通并提交。第三步合上代码用一句话给自己讲清楚“为什么跳过num - 1存在的元素不会漏掉最优解”能流利讲出来才算真正掌握了。我前两遍刷的时候就是跳过了第一步直接背最终代码结果面试时面试官问“复杂度为什么是O(n)”我当场卡壳。后来老老实实把暴力版本写了一遍再对比优化版所有疑问都消失了。这道题如果只是背下来遇到面试追问很容易露馅但如果你真的理解了起点过滤的逻辑它反而能成为你展示思路清晰度的好机会。