最长连续序列Longest Consecutive Sequence这个题目最近又被算法面经和刷题榜单翻出来反复考。光看热搜里那句“给定一个无序数组找出最长连续递增子序列的长度”不知道多少人第一反应是“这不就是最长递增子序列吗”结果一写代码才发现题意完全对不上。我先说结论这类题看着简单但“连续”两个字在不同题目里的含义差着十万八千里。LeetCode 128 的原题里“连续”指的是数值上的连续比如 1、2、3、4 这种差值为 1 的数跟位置、相对顺序一点关系都没有。这篇文章把这道题从题意辨析、排序解法的局限、O(n) 哈希表方案到边界条件和延伸变体完整拆一遍顺手把“最长连续递增子序列”这个兄弟题目也讲清楚看完你就能直接上手写代码。1. 先把题意吃透这里的“连续”不看位置只看数值1.1 一个例子直接建立直觉给一个无序数组 [100, 4, 200, 1, 3, 2]最长连续序列的长度是多少答案是 4。因为数组里存在 1、2、3、4 这 4 个数值上连续的数。注意它们在原数组中的位置是打乱了的1 在倒数第三个2 在最后3 在倒数第二个4 在第二个这些都不影响结果。换句话说这个问题的本质是把数组看成一个集合找出这个集合里能构成的“公差为 1 的最长等差序列”元素个数。这个第一直觉特别重要。很多初学者会下意识地把“连续”理解成“在原数组里位置相邻”然后去做一次遍历比较相邻元素把 [1, 2, 3, 4] 这样打乱的输入判断成答案是 1。这种错法我在评审代码时见过不少次属于题意理解上的典型翻车现场。所以动笔写代码前先花 30 秒确认这个“连续”到底是数本身的连续还是位置的连续这道题是前者。1.2 三个长得像但不是一回事的题经常混在一起的有三个题我做了个表格一眼就能看出区别题目要求典型输入与输出最优复杂度最长连续序列128数值连续位置随意[100,4,200,1,3,2] - 4哈希表 O(n)最长连续递增子序列674原数组位置连续 数值递增[1,3,5,4,7] - 3一次遍历 O(n)最长递增子序列300保持原顺序可跳元素[10,9,2,5,3,7,101,18] - 4DP二分 O(n log n)拿输入 [1, 2, 3, 1, 2] 来演示三种题目的差异最长连续序列的视角集合是 {1, 2, 3}答案是 3最长连续递增子序列的视角1,2,3 是连续的一段后面的 1,2 是另一段最长还是 3最长递增子序列的视角可以跳着选比如第 4 个位置的 1 和第 5 个位置的 2 也构成递增但最长仍然是 1,2,3答案还是 3。再换一个 [2, 1, 3]最长连续序列集合 {1,2,3}答案是 3最长连续递增子序列2 到 1 下降1 到 3 上升所以最长的连续递增段是 [1,3] 或 [2]答案是 2。区别一下就出来了吧。题目描述里如果混着“递增”“子序列”这些词先停下来想清楚它到底要哪个答案这是刷题时最容易被坑的地方。1.3 重复元素的坑去重不是可选项数组 [1, 2, 0, 1]最长连续序列的长度是多少正确答案是 3也就是 0、1、2 这三个数。1 出现了两次但连续序列的长度不能按 4 算重复元素不能多算一次。这就是为什么最终方案必须用集合而不是线性表把数组转成集合后重复元素自动消除遍历时每个数值至多被处理一次。如果保留所有重复元素统计时会重复计数后面还得专门做去重判断纯属给自己添堵。我见过有人真的在排序解法里用“跳过重复元素”的方式处理也能过但那是因为排序天然把相同元素排在一起换个思路就没这么好办了。2. 排序解法能保底但过不了 O(n) 这一关2.1 排序后一次遍历思路确实简单很多人看到这题的第一反应就是排序。确实排序之后问题被大幅简化只要从左往右扫一遍维护当前连续段的长度。具体逻辑是对数组从小到大排序用一个变量 cur 记录当前连续段的长度初始为 1遍历排序后的数组比较当前元素和前一个元素如果相等跳过重复元素不能算两遍如果差值为 1cur 加 1更新答案否则cur 重置为 1开始一个新的连续段。Python 实现大概是这样的def longestConsecutive_sort(nums): if not nums: return 0 nums.sort() cur 1 res 1 for i in range(1, len(nums)): if nums[i] nums[i - 1]: continue elif nums[i] nums[i - 1] 1: cur 1 res max(res, cur) else: cur 1 return res这段代码能通过大多数测试用例。时间复杂度是 O(n log n)排序是瓶颈空间复杂度取决于排序算法Python 内置的 TimSort 最坏情况是 O(n)。2.2 复杂度账O(n log n) 到底差在哪题目明确要求 O(n)O(n log n) 就是不合格。有人会抬杠n log n 不是也挺快十万个数据点也就一百多万次操作纠结这个干什么这不是跑不跑得动的问题而是理论边界的差异。当数据量逼近千万、亿级别甚至数据是源源不断流入的O(n) 和 O(n log n) 的差距会被迅速放大。而且面试官考这道题本质上是看你能不能识别出“集合查询”这个数据结构特性而不是背一个排序模板。另一个更现实的点很多场景下数组不能随便排序。比如数组元素代表业务对象的主键索引排序会破坏原来的关联关系或者原始数据本身是只读的。这时如果做一份拷贝再排序时间和空间的开销都上去了有点得不偿失。2.3 从面试角度看这个答法能兜底但不够亮眼老实说如果面试时实在想不出来先给出排序解法主动说明复杂度不达标再补一句“我可以用哈希表优化到 O(n)”这个流程在面试里是加分的。怕的是只丢出排序解法就停住还觉得已经做完了——那我作为面试官基本会追问“能不能不排序”。这一问就是这道题真正的分水岭。后面要讲的哈希表方案才是这道题想考察的核心内容。3. O(n) 的核心思路哈希集合加起点剪枝3.1 朴素想法对每个元素往后数为什么是 O(n²)一个很自然的脑洞是遍历每个元素 num然后依次检查 num1、num2…… 在不在数组里数到断了为止。这个朴素做法的时间复杂度是 O(n²)。最坏情况数组是 [1, 2, 3, ..., n] 的乱序排列对 n 个起始元素每个都要数 n 步。就算外层用一个集合来判断“在不在”整体仍然是 O(n²)因为大量重复的“往后数”动作被反复执行。优化方向其实很明确能不能让每个元素只被“数”一次3.2 关键剪枝只有序列起点才配启动内层循环答案是能。观察一下“往后数”的过程对于一个连续序列比如 1、2、3、4它的起点是 1。如果我们从 2 开始数得到的是 2、3、4从 3 开始数得到 3、4从 4 开始数得到 4。这些都是同一个序列的“子集前缀”。换句话说如果当前元素 num 的前一个数 num-1 也存在于数组中那么从 num 开始数一定能数出的只是某个更长序列的子集纯属浪费时间。所以剪枝规则就一句话只有 num-1 不在集合中的 num才启动内层循环往后数。这个剪枝的威力是巨大的。有了它每个元素最多被内层循环访问一次一个长度为 L 的连续段只有起点会触发一次内部扫描而且这次扫描恰好覆盖这个段里的 L 个元素。如果有 K 个连续段内部扫描的总次数就是 K 个段的长度之和也就是去重后的数组长度 n。外层循环本身每个元素也只会过一遍所以整体复杂度是 O(n)。我打个比方这就好比在操场上清点几排队列。如果你从每排第一个开始报数每个人只会被报到一次如果你从队伍中间开始那前面几个人就会被反复报到。想想是不是这么回事。3.3 整个算法流程用大白话说就是把数组转成哈希集合 HashSet同时完成去重遍历集合中的每个数 num如果 num-1 不在集合中说明 num 是某个连续段的起点从 num 开始依次检查 num1、num2…… 在不在集合中用计数器 length 记录从起点数出来的长度更新全局最大值返回最大值。为什么用集合而不是其他数据结构因为集合的“是否存在”查询是平均 O(1) 的而且不受数值范围限制。数组下标的做法在这题里不好使元素可能是负数比如 [-3, 0, 1]可能是特别大的数10^9根本没法映射到紧凑的数组下标。4. 代码落地Python 与 Java 实现细节4.1 Python 版核心逻辑就一个循环def longestConsecutive(nums): num_set set(nums) res 0 for num in num_set: if num - 1 not in num_set: # 只从连续段的起点开始 length 1 while num 1 in num_set: num 1 length 1 res max(res, length) return res这里有三个容易踩的点。第一遍历的是num_set而不是原数组nums。虽然两者都能跑出正确结果但遍历集合可以确保重复元素不会被当成多个起点或中间节点重复处理。示例 [1, 2, 0, 1] 里如果遍历原数组1 会在第一次出现时被处理一次第二次出现时又处理一次逻辑上多了很多绕弯。第二内层循环里直接改num的值没有问题因为 num 只是循环变量的拷贝不会影响集合本身。但见过有人习惯性地在 while 里写num 1后又去更新外层 num结果死循环。保持上面这份代码的写法就是最稳的。第三res的初始值。空数组要返回 0所以初始化 res 0只要数组非空最长长度至少是 1后面res max(res, length)会自然收束。4.2 Java 版注意集合选择与溢出风险class Solution { public int longestConsecutive(int[] nums) { SetInteger set new HashSet(); for (int num : nums) { set.add(num); } int res 0; for (int num : set) { if (!set.contains(num - 1)) { int cur num; int length 1; while (set.contains(cur 1)) { cur 1; length 1; } res Math.max(res, length); } } return res; } }Java 里有两个细节值得单独说。一是集合类型。很多 Java 新手会在这个场景用 ArrayList 然后list.contains()这是灾难性的因为 ArrayList 的 contains 是 O(n)整体复杂度瞬间退化成 O(n²)。必须用HashSet它的 contains 平均复杂度才是 O(1)底层是哈希表跟 Python 里的 set 一个道理。二是cur 1的溢出问题。虽然 LeetCode 的数据范围用 int 不会踩到但如果数据是 Long 类型cur 1在cur Long.MAX_VALUE时会溢出变成负数导致 while 条件判断错乱。严谨的写法是在判断前转成更大范围的类型比如 long。Python 没有这个问题因为它的整数是任意精度的。4.3 边界条件一网打尽我整理了一份覆盖大多数面试追问的测试用例表输入预期输出说明[]0空数组[5]1单元素[1, 2, 3, 4, 5]5全局最长一段[5, 4, 3, 2, 1]5乱序但不影响[1, 2, 0, 1]3重复元素要去重[100, 4, 200, 1, 3, 2]4经典样例[0, 3, 7, 2, 5, 8, 4, 6, 0, 1]9多段连续取最长[-3, -2, -1, 0, 1]5负数参与连续我实测过上面所有用例Python 和 Java 两个版本输出完全一致。边界处理核心就两条空数组特判、重复元素靠集合去重。其他特殊情况基本都被哈希集合这个设计天然消化掉了。5. 高频错误与延伸方向把一道题变成一类题5.1 四个高频错误我帮你提前排掉在评审代码和自己刷题的过程中我总结出四个最常见的问题错误做法后果正确做法用 List.contains 判断存在复杂度退化为 O(n²)大用例直接超时用 HashSet/Set遍历原数组而不是去重后的集合重复元素被重复计数逻辑绕遍历 set所有元素都启动内层循环最坏 O(n²)剪枝失效只对 num-1 不在集合的 num 启动把“连续”理解成“位置连续”答案直接出错明确题意是数值连续其中第三个错误最隐蔽。代码能跑、小用例能过一上大数据就超时根本原因就是漏了“起点剪枝”。这也是整个 O(n) 方案的精髓看似只多了一次num-1的查询实际上把大量无效计算挡在了门外。举个具体的排查例子。有一次我把if num - 1 not in num_set去掉了跑小用例全对自己还挺得意结果数据量到十万级别程序明显卡顿。加回来之后耗时从几百毫秒降到几十毫秒。这个剪枝不是优化技巧而是这个算法能被称为 O(n) 的前提条件。5.2 另一个 O(n) 流派并查集思路哈希表是解决这题最主流的思路但不是唯一思路。用并查集Union-Find也可以做到近似 O(n)先把所有元素放进集合然后对每个 num如果 num1 也在集合里就把 num 和 num1 所在集合合并并维护每个集合的 size最后取最大 size。并查集的优点是“一次性把关系建完之后随便查”缺点是代码量比哈希表方案大不少对于这道题属于杀鸡用牛刀。我一般只在讲并查集专题时顺带提它日常刷题用哈希表方案就够了。但如果你在面试中主动说出“其实并查集也能做”这会是加分项前提是你能把路径压缩和按秩合并讲清楚别给自己挖坑。5.3 回到热搜描述里的“最长连续递增子序列”如果题目真的写成“无序数组中找最长连续递增子序列的长度”那要辨析一下。这通常是“位置连续 数值递增”的版本对应 LeetCode 674。它的经典写法是一次遍历维护当前递增长度def findLengthOfLCIS(nums): if not nums: return 0 cur 1 res 1 for i in range(1, len(nums)): if nums[i] nums[i - 1]: cur 1 res max(res, cur) else: cur 1 return res注意这里比的是nums[i] nums[i - 1]不要求差值为 1只要求严格递增。输入 [1, 3, 5, 4, 7]答案是 31,3,5 或 4,7 取较长。这和“最长递增子序列LIS”又不相同——LIS 允许跳着选元素且保持原顺序解法通常是动态规划加二分复杂度 O(n log n)。一句话总结这几者的区别最长连续序列看的是数值本身连不连LCIS 看的是原数组里一段一段的升降LIS 看的是能跳出多长的上升链。这三道题经常被放在同一次面试里横向考察搞清楚差异比多背十个模板都管用。5.4 流式数据场景下的进阶思考聊一个延伸的实际问题。哈希表方案的空间复杂度是 O(n)如果数据不是一次性给全而是像日志那样源源不断流入的内存就会成为瓶颈。这种情况一般有两条路一是按数值分桶维护每个桶内最长的连续区间再定期合并相邻桶二是用位图bitmap记录出现过的数每个数只占 1 bit对数据范围可控的场景非常有效。比如数据范围限定在 0 到 10^7 之间一张 1.25 MB 的位图就能搞定全部去重和存在性判断。不过说实话绝大多数面试和业务场景到不了这一步。知道有这几个方向真遇到时再深入研究就好不用在初期把时间耗在这里。我个人刷题的习惯是每做完一道题都要问自己三件事它和哪些题长得很像但解法完全不同最优解背后的剪枝动机是什么如果数据规模或者数据形态变了方案还成不成立最长连续序列这道题恰好把三点全占了所以我一直觉得它是面试复习里性价比很高的一道题。把这些想透你收获的就不只是这一题的答案而是一整套处理“存在性查询”和“段合并”问题的思路。