力扣128最长连续序列：哈希表如何将复杂度优化到O(n)

在力扣刷题的过程里128“最长连续数列”属于那种让人印象特别深的题目。它表面上看是一个数组遍历的问题可实际上考察的是对时间复杂度的敏锐程度、对数据结构的选择以及面对数字集合时能不能跳出“排序惯性”的思维定式。这道题被归类为中等难度但很多第一次接触的人都会掉进“先排序再求解”的陷阱里等看到题目要求O(n)复杂度时才恍然大悟——常规思路在这里行不通必须换个角度找突破。我的建议是所有准备算法面试、想巩固哈希表应用、或者想训练自己“在约束条件下重新设计解法”的人都应该好好啃这道题。它不像动态规划那样需要复杂的状态推导也不像图论那样需要大量的模板记忆恰恰卡在“思维转换”这个节点上同一个问题换一种组织数据的方式算法复杂度就能从O(n log n)变成O(n)。这篇文章我会把这道题从题意拆解、三种主流解法、边界条件、到面试现场的思路展示完整走一遍。1. 题意解读与核心难点拆解1.1 题目到底在问什么题目一般是这样描述的给定一个未排序的整数数组nums找出数字连续的最长序列这里的“连续”指的是数值上依次递增比如1、2、3、4而不要求它们在原数组中紧挨着的长度并且要求算法时间复杂度为O(n)。举个例子nums [100, 4, 200, 1, 3, 2]答案是4因为能组成的最长连续数列是1 - 2 - 3 - 4。单看这个例子很多人第一反应是“这不就是排序吗排完序数一数不就出来了。”确实排序可以解但题目明确要求O(n)时间复杂度这就是核心矛盾点基于比较的排序最快也是O(n log n)内存排序比如计数排序虽然可能达到O(n)但受限于数值范围面对分散的大整数反而更慢。所以我们需要一种不依赖全序比较的思考方式。1.2 所谓O(n)限制的真正含义从面试角度来说O(n)这个约束是整道题目的灵魂。它传达的信息是你最多只能对数组进行有限次数的遍历并且每个元素的处理基本是常数时间。一旦你尝试全局排序复杂度就失控了。理解O(n)约束还有一个关键点它意味着我们的算法不能出现“对每个元素再去全局寻找匹配项”这样类似O(n²)的嵌套遍历。我们要把“查找”的代价摊薄到O(1)这就是哈希表登场的理由。还有一点值得想清楚这里的n是数组长度但数组元素的值域可以非常大比如包含-10^9到10^9这样的极值。这决定了我们不能用数组下标来直接映射数值必须用哈希表在Python中是set在C中是unordered_set。本质上是“用空间换时间”把数值本身变成查询的键。1.3 相似题型的区分为什么有人会联想到“腐烂的橘子”热搜词里有“leetcode 994腐烂的橘子”和“leetcode 073 爱吃香蕉的狒狒”它们和128题不是同一种题型。994是典型的BFS多源层序遍历773则属于二分答案。而128题属于“集合/哈希表 线性扫描”题型。把易混淆的题放在一起看能帮你更快识别每道题的核心方法论。腐烂的橘子和128题的核心区别在于994题存在“扩散”的层次关系必须用队列维护每一分钟感染的橘子而128题的连续数列只关心数值的连续性与位置、顺序、扩散完全无关。这也是为什么哈希集合比队列更合适因为它只需要迅速判断某个数值是否存在而不需要维护顺序关系。2. 三种主流解法对比分析2.1 排序解法最直观但面试常被否排序解法的逻辑非常朴素先对数组排序然后遍历排序后的数组若nums[i] nums[i-1] 1则当前连续长度加1若相等重复元素则忽略否则重置当前长度为1。每次更新最大长度。def longestConsecutive_sort(nums): if not nums: return 0 nums.sort() longest 1 cur 1 for i in range(1, len(nums)): if nums[i] nums[i-1] 1: cur 1 elif nums[i] nums[i-1]: continue else: cur 1 longest max(longest, cur) return longest这段代码正确性没问题边界条件也考虑到了时间复杂度是O(n log n)。但面试官会追问“能不能做到O(n)”。这时候你如果答不上来这道题的得分就会大打折扣。所以我一直强调刷题不能只满足于“通过”要理解题目约束背后的用意。排序解法最大的价值是帮助我们确认题目理解无误但绝不是最优解。2.2 哈希集合解法O(n)的关键思维转换这是这道题最漂亮的解法思路可以概括为三句话把数组中所有元素放进一个哈希集合HashSet。遍历集合中的每个数字num如果num - 1不在集合中说明num是某个连续序列的起点。从num出发不断检查num 1,num 2... 是否在集合中统计连续长度。核心洞察在于只有序列起点才值得展开统计。如果num - 1已经在集合中num本身就是某个更长子序列的一部分它作为起点去统计必然是次优的直接跳过即可。这样一来每个数字最多被访问两三次——一次作为外层遍历一次在从起点扩展时被内层数到整体复杂度就是O(n n) O(n)。很多初学者会疑惑“这难道不是嵌套循环吗为什么会是O(n)”关键在于内层循环并不是对每个外层元素都会完整执行只有当一个元素是序列起点时内层才会延伸而且一旦某个元素被内层访问过它就不会作为另一个序列的一部分再被遍历统计。总的工作量本质上就是数组中出现的所有连续段的总长度每个连续段的长度加起来不超过n所以摊下来每个元素仍是常数操作。下面以nums [100, 4, 200, 1, 3, 2]模拟一遍集合{1, 2, 3, 4, 100, 200}遍历到10099不在集合中100是起点往下找101不存在长度1。遍历到43在集合中跳过因为它不是起点。遍历到200199不在集合中200是起点长度1。遍历到10不在集合中1是起点往后找2、3、4长度4。遍历到32在集合中跳过。遍历到2跳过。最终答案是4。代码实现Python示例def longestConsecutive(nums): num_set set(nums) longest 0 for num in num_set: if num - 1 not in num_set: current_num num current_streak 1 while current_num 1 in num_set: current_num 1 current_streak 1 longest max(longest, current_streak) return longest这段代码看起来极其简洁但每一步都踩在关键点上。使用set(nums)会自动去重重复元素不会干扰连续性判断这是容易忽略但非常重要的细节数组[1, 2, 2, 3]的最长连续数列长度应该是3如果不去重排序解法里也相应做了跳过重复元素的处理而哈希集合天然规避了重复计数的问题。2.3 并查集拓展一种不常见的优化视角掌握哈希集合解法后可以了解下并查集Union-Find的思路虽然不推荐在面试里首选写它但能加深对“连续关系”本质的理解。并查集的切入角度是数字与相邻数字之间存在连接关系。初始化时每个数字的父亲指向自己遍历每个数字若num 1存在则把num和num 1合并。最后统计每个集合的大小最大的就是答案。原理上是可行的时间复杂度也可以做到近似O(n)但实现起来比哈希集合解法复杂得多需要维护父节点数组、路径压缩、按秩合并等而且在值域很大的情况下还需要用哈希表来替代数组存储父亲节点整体代码量和出bug的概率都高出一截。它最大的应用价值是帮助理解“用什么数据结构表达元素之间的连接性”。但对于这道题哈希集合的代码已经非常优雅并查集属于过犹不及的解法。如果面试中被要求“换一种解法”提并查集可以展示知识广度但不要作为主解。一般来说主解应当是最简单、最直观、最容易证明正确性并且复杂度最优的那个方案哈希集合解法完美满足这些标准。2.4 三种解法直观对比速查表为了便于记忆这里整理一个对比表格解法时间复杂度空间复杂度代码复杂度面试推荐度核心思想排序法O(n log n)O(1)或O(n)低适合热身/验证排序后线性扫描哈希集合O(n)O(n)低强烈推荐找序列起点只向右扩展并查集O(n·α(n))O(n)高拓展了解数值连接性合并3. 实战实现全流程记录3.1 语言选型与代码细节注意点算法题的实现选语言要从目标面试岗位出发。如果是Python代码最简洁适合快速沟通思路如果是Java/C讨论哈希集合的实现细节会更有话聊。我用三种语言各写一版方便对照学习。Python版本简洁适合沟通class Solution: def longestConsecutive(self, nums: List[int]) - int: nums set(nums) best 0 for x in nums: if x - 1 not in nums: y x 1 while y in nums: y 1 best max(best, y - x) return bestJava版本注意哈希表的选择class Solution { public int longestConsecutive(int[] nums) { SetInteger set new HashSet(); for (int num : nums) { set.add(num); } int longest 0; for (int num : set) { if (!set.contains(num - 1)) { int curNum num; int curStreak 1; while (set.contains(curNum 1)) { curNum; curStreak; } longest Math.max(longest, curStreak); } } return longest; } }要注意的是Java中遍历HashSet的同时向集合添加元素会抛异常但这里只是读取没有修改所以是安全的。HashSet的contains方法平均O(1)最坏情况下哈希冲突会退化但工程场景下基本不会出现。C版本关注性能和内存class Solution { public: int longestConsecutive(vectorint nums) { unordered_setint s(nums.begin(), nums.end()); int longest 0; for (const int num : s) { if (!s.count(num - 1)) { int cur num; int len 1; while (s.count(cur 1)) { cur; len; } longest max(longest, len); } } return longest; } };C的unordered_set平均也是O(1)查找但极端情况下可能退化不过刷题场景不需要过度纠结。3.2 模拟一次完整调试过程假设测试用例nums [0, -1, 9, 8, 7, 10, 11, 12]我们手动走一遍先转成集合{-1, 0, 7, 8, 9, 10, 11, 12}。取-1检查-2是否存在不存在所以-1是一个起点。扩展-1 - 0存在长度21不存在结束。当前最长2。取0检查-1存在跳过。取7检查6不存在起点。扩展8、9、10、11、12连续长度6。取8检查7存在跳过。后面同理。最长结果是6。这个用例同时展示了负数处理、跨0连续、多段共存三种情况。如果是空数组[]集合为空循环不执行返回0能直接通过边界。如果数组全是重复元素比如[5, 5, 5]转成集合后只有1个元素返回1——这也是正确答案因为单一数值算作长度为1的连续数列。3.3 复杂度严谨推理很多人对“为什么内层循环总体是O(n)”理解不够深入这里给出严谨解释假设集合中所有元素被划分成若干条连续段。设这些连续段的长度分别为L1, L2, ..., Lk显然sum(Li) mm为集合大小不超过n。外层循环会遍历每一个元素但当且仅当它是所在连续段的最小值时内层循环会从该段起点一路扫到终点扫描长度为Li。所以内层循环的总步数是sum(Li) m外层循环是m总时间复杂度O(m) O(n)。这个证明很关键面试时如果被追问复杂度把这个逻辑讲清楚会比“很明显是O(n)”有说服力得多。空间复杂度方面哈希集合存储了所有不重复的数字所以最坏情况是O(n)。如果题目允许修改原数组理论上可以用“原地标记”的方式压缩空间但数值范围不可控标记负数、正数的手段过于tricky且容易出错工程上不推荐面试中提一句即可不必深入。4. 面试现场的高分答题节奏4.1 先展现思考路径而不是直接写代码我在模拟面试中最常看到的情况是候选人一上来就写set(nums)然后开始for num in set写完了但讲不清楚为什么这样是对的。这很可惜因为面试官真正想看的不是代码本身而是你面对一个带约束的问题时如何思考。理想的答题节奏应该是这样先复述题意确认“连续”的定义不需要元素在原数组相邻。提一下排序解法O(n log n)作为基线思路。马上指出题目要求O(n)所以思考如何用哈希集合将查询降为O(1)。抛出关键洞察只有在num - 1不存在于集合时才把num当作起点开始统计。解释复杂度推导。最后流畅地写出代码。整个过程不超过5分钟但展现了从约束推导思路的能力。我经常说刷题的价值不在于背答案而在于练习这种“从约束条件出发倒推数据结构与算法”的思维方式。4.2 面试官常见的追问与应对如果面试官想挖深通常会追问这样几个问题如果数组非常大内存装不下怎么办此时可以讨论外部排序或分布式计算但一般不会深入知道方向即可。如果数组是数据流数字不断进入如何维护最长连续数列这引出了在线算法的概念思路变成维护多个区间的端点新数字到达时判断能否扩展已有区间需要用到有序结构如平衡树复杂度变为O(log n)。这个延伸很有区分度能讲出来就是加分项。如果要求输出的不是长度而是具体的连续数列此时哈希集合解法稍作改动记录序列的起始和结束值即可。4.3 常见题解内容之外的延伸学习路径聊“基本计算器 leetcode”也是131和224题跟128题不在一个方向但可以说明一个问题做题要学会归类和对比。我给自己的刷题习惯是每道题写出题解后记录“这道题用到的最关键数据结构是什么、最关键的剪枝条件是什么、跟之前哪道题有相似逻辑”。比如128题最关键的是“用哈希集合把查找从O(n)降到O(1)”跟它思维上有亲缘关系的还有“最大连续元素个数”的变体如二维矩阵里的连续1最长长度、区间合并类题目比如合并区间、插入区间以及利用“只处理起点”思路的很多哈希类题目。这样长期积累下来体系感会越来越强。比如热词里的“leetcode热门100题”和“leetcode题解”其实都是很好的学习资源但只看题解不动手是不行的尤其像128这种“代码10行、思维卡半天”的题目真正动手写一遍、调试一遍记忆才会深刻。5. 常见错误、边界条件与调试技巧5.1 高频易错点盘点先空数组[ ]返回0漏掉这个判断在Python中不会报错但返回结果会是错误值必须注意。重复元素[1, 2, 2, 3]的最长长度是3如果排序解法里忘了跳过相等元素会得到错误长度。哈希集合解法天然去重但如果面试时你用的是排序法这一步很容易踩坑。负数边界[-2, -1, 0, 1]的答案是4负数同样能参与连续序列注意不要因为下意识只考虑非负数而出错。超大整数[10^9, 10^9 1]这种情况下如果用数组下标映射内存会爆炸只有哈希能解决。重复起点判断必须同时检查num - 1存在与否而不是只依赖num 1是否存在。如果把判断条件写反成if num 1 not in num_set时间复杂度大概率退化为O(n²)每个元素都往左扩展务必留意。5.2 调试小技巧本地调试时我推荐多准备几组特殊测试数据空数组[]单元素数组[5]全重复数组[7, 7, 7, 7]连续序列位于数组末尾[1, 3, 2, 4, 5, 0]包含负数、零、正数的混合[-1, 0, 1, 3, 4, 5]测试时可以在循环里临时打印num, num - 1 in set, num 1 in set等调试信息很容易看清哪些元素被当成了起点。我在初学时踩过的一个坑是用列表代替集合导致in操作变成O(n)整体复杂度退化为O(n²)而不自知。如果写完代码发现大数据用例超时第一反应就应该是检查in操作的容器是不是集合。5.3 避免死循环与无限扩展由于我们只在集合中查找数字不会修改集合所以内层循环while current_num 1 in num_set一定是有限次数的最多扩展到序列终点。但如果代码写成了while num 1 in num_set: num 1然后外部又对原始num进行操作就可能产生逻辑混乱。建议做法是引入新变量current_num表示当前检查的数字避免修改外层迭代变量这是新手最容易犯的错。6. 难度变体与后续思考6.1 二维矩阵版最长连续数列把问题扩展到二维矩阵每个格子有数字上下左右相邻且数字相差1视为连续。此时最长连续数列就是经典问题“矩阵中的最长递增路径”解法变成了DFS 记忆化搜索复杂度O(mn)。这个变体在“leetcode周赛430”这类比赛里经常出现本质从“哈希集合线性扫描”变成了“图的记忆化深搜”。对比之下就能体会128的限制有多么独特一维数组没有结构上的邻接关系全凭值域查找二维矩阵则有了明确的“邻居”概念DFS的顺序变得重要。这种维度上的变化会让你对算法问题本身有更立体的把握。6.2 数据流不间断版本的维护思路如果数据是一个流数字不断到达你没法一次性看到全部元素。这时要维护“连续区间”的端点可以用有序结构或区间合并的思路。新数字到达时查它左右相邻数字是否已有区间存在如果有则合并或扩展最终记录最大长度。这个思路常用于系统设计面试中的实时统计场景实际业务中比如监测用户连续登录天数本质上也是维护连续区间的长度。6.3 我对这道题的整体评价与学习建议我从128题中学到的最重要的东西不是哈希集合API怎么用而是“当你发现自己的解法包含排序时先停下来想一想是否真的需要全局有序”在很多算法问题里排序是一种万金油做法但一旦题目加上O(n)的约束就逼着你放弃它去寻找更轻量的工具。哈希集合本质上是一种“只需要知道某元素是否存在、不关心其顺序”的数据结构这道题恰好展示出这种结构如何在算法中发挥核心作用。另一个体会是对于看似简单的题最好能给出完整、严谨的复杂度证明。这不仅能帮你在面试中从容应对追问也会推动你把“我觉得应该对”变成“我确定它是对的”。刷题过程中每一步都要能解释“为什么”。这道题完全值得你多刷几次第一遍按自己的直觉写第二遍再优化到O(n)第三遍把复杂度证明讲给朋友听——能讲明白才算真正掌握。