复杂度剖析)
刷 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]来说10099不在99 不可能是起点不对100 是起点因为没有 99。43在所以 4 不是起点跳过。200199不在200 是起点但向后只有 200 一个长度 1。10不在1 是起点向后可以找到 2、3、4长度 4。32在跳过。21在跳过。只有起点才会进入 while 循环往后数。这样一来每个数最多被发起一次扫描而扫描会覆盖一条完整的链链上的每个元素又只会被扫描一次。后面会详细证明这就是 O(n)。2.2 关键代码与逐行解析这是 Java 版的标准实现也是我推荐面试时手写的版本class Solution { public int longestConsecutive(int[] nums) { SetInteger 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的操作。有些同学第一反应是 ArrayListcontains是 O(n) 线性查找。一旦用上整个算法立刻变成 O(n²)数据一大就超时。这属于基础 API 复杂度不熟悉的问题。第四类递归写法。有人试图用递归或栈去“展开”连续链比如对每个数递归寻找相邻数。这个过程如果不加记忆化每个节点会被重复展开多次复杂度很容易爆炸。能用迭代解决的算法题优先用迭代。4.3 几种语言的实现注意事项如果你用 Java要注意HashSet的泛型类型。LeetCode 的方法签名是int[] nums直接迭代即可。使用new HashSet()时最好初始化容量比如new HashSet(nums.length * 2)可以减少扩容带来的性能损耗不过 LeetCode 上这个差异不大。C 选手用unordered_setint注意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 只是一个开始它背后的复杂度思维方式才是你真正值得带走的东西。
