力扣128最长连续序列：哈希集合O(n)解法与易错点全解析

说实话力扣128这道《最长连续序列》是我在准备算法面试时印象最深的一道题。题目要求很短逻辑看起来也不绕但第一次动手写代码的人十个里有八个会下意识“排个序扫一遍”了事——然后被一句“你能做到O(n)吗”给问住。我自己也是从暴力解法一路踩坑过来的所以这篇笔记不打算只贴一份AC代码而是把题目拆透、把三种解法的思路和复杂度账算清楚再把我实际踩过、以及帮别人debug时见过的坑都摆出来。适合正在刷力扣热题100的Python学习者也适合那些“这道题我看过题解但还是不会写”的朋友。1. 题干拆解连续序列判定到底在判什么1.1 题目原文与示例解析题目给一个“未排序的整数数组”要求找出“数字连续的最长序列”的长度并且特意强调不要求序列元素在原数组中连续。看示例最容易体会这句话的意思。示例1是[100,4,200,1,3,2]最长连续序列是[1,2,3,4]长度是4。注意数组里这些数字的原始顺序是“100,4,200,1,3,2”1、2、3、4在数组里的位置并不相邻但它们按数值排确实是连续的一串。示例2是[0,3,7,2,5,8,4,6,0,1]最长的是[0,1,2,3,4,5,6,7,8]长度9。这里还有一个非常容易忽略的细节数组里有两个0但连续序列里同一个数字只能出现一次。也就是说去重是绕不开的一步。1.2 “连续”到底指什么值域连续而非位置连续这题的“连续”是值域上的连续跟数组下标一点关系都没有。我自己最早做这题的时候对着示例反复找“4后面为什么是3”这种位置关系绕了很久才醒悟过来——题目根本不关心数字在数组中怎么排列。一个比较贴切的类比是把数组里的每个数看成一块写有编号的积木散落在一堆盒子里。题目要你找出编号最大的连续区间比如1到5这五块编号连在一起的积木。积木在哪个盒子里、哪个位置完全不影响判断。这个认知极其重要。因为一旦建立“序列位置连续”的惯性思维你可能就会往“双指针滑窗”“前缀和”这类方向想但那些思路在这里全部跑偏。正确做法的第一步就是先把位置连续这个刻板印象清掉。1.3 为什么O(n)是这道题的死命令题目最后通常会有一句设计并实现时间复杂度为O(n)的算法。这句话至少透露两个信息。第一排序这条路被堵死了。任何比较排序的下界都是O(nlogn)你不可能排完序还声称自己做到了线性。第二它暗示了一个方向想做到O(n)必然要有一个“常量时间内回答某个数字是否存在”的手段。数组的线性查找做不到二分查找也依赖有序唯独哈希表在Python里就是set或dict能稳定做到平均O(1)的成员查询。所以看到O(n)这个要求基本可以锁定思路先把数组转成set后续判断全部走哈希查询。这不是什么玄学是复杂度要求倒推出来的结论。2. 暴力解到排序解先建立直觉再谈优化2.1 暴力三重循环正确但没用的解法很多教程会跳过暴力解直接给最优解。但我建议你先写一遍暴力因为它能帮你确认两件事查询得用哈希结构起点枚举必须剪枝。暴力的思路是枚举每个数字x作为起点不断检查x1、x2……是否在数组里统计最长长度。如果查询数组用Python的x in nums每次是O(n)开销加上外层起点枚举和内层延伸总复杂度会到O(n^3)级别。把数组先转成set之后查询变成O(1)复杂度降到O(n^2)。代码大概长这样def brute_force(nums): s set(nums) ans 0 for x in nums: cur x cnt 0 while cur in s: cnt 1 cur 1 ans max(ans, cnt) return ans这个代码在LeetCode上大概率超时但它把问题结构暴露得很清楚瓶颈已经不在查询而在于每个数字都被当成起点重复往后数。比如[1,2,3,4,5]从1开始数一次是5从2开始又数一次是4从3、4、5各自再数……这些冗余计算完全没意义。下一步优化的方向就是想办法只从连续块真正的左端点开始数。2.2 排序解法的代码与复杂度排序解法是很多人“明知不是最优但忍不住想用”的答案因为它实在是太直观了。排完序后数值连续的数字会自然挨在一起扫一遍就能统计出最长连续块的长度。def longestConsecutive_sort(nums): if not nums: return 0 nums.sort() max_len 1 cur_len 1 for i in range(1, len(nums)): if nums[i] nums[i - 1]: continue if nums[i] nums[i - 1] 1: cur_len 1 else: cur_len 1 max_len max(max_len, cur_len) return max_len时间复杂度O(nlogn)因为排序是绝对大头空间复杂度O(1)前提是允许原地修改nums。实际刷题时排序解大部分测试用例都能跑过去因为LeetCode给的输入规模不算极端。但面试里如果只给这一版通常过不了关——面试官下一句大概率是“进阶要求写的是O(n)你怎么看”还有一个容易被忽略的工程细节如果在实际项目里不允许修改原始数组你就得先copy一份再排序空间复杂度立刻变成O(n)。所以面试时可以主动问一句“原数组可以改吗”这个问题本身就加分。2.3 排序解法的隐藏问题重复元素与末尾段排序解有两个特别经典的坑我见过不下五个人在这里翻车。第一个坑是重复元素处理。假如数组是[1,1,1,1]如果没有nums[i] nums[i-1]这个跳过逻辑扫描时会认为1后面还是1连续长度不断累加最后返回4。正确答案显然只有1。所以重复值必须直接continue不能让它参与“连续”计数。第二个坑是末尾连续块的结算时机。如果你把max_len的更新只放在else分支也就是“遇到断点才结算”那么当最长连续块恰好延伸到数组末尾时循环从头到尾没进入过elsemax_len就永远不会被更新。比如[0,1,2,3,4]中途一个断点都没有cur_len一路加到5但max_len可能还是初始值1。解决这种bug最土也最有效的办法就是每一轮都更新max_len不要依赖“结算”这种延迟动作。这个经验放到后面的哈希解里同样适用能立刻做最大值比较就不要攒着最后再算。3. 哈希集合O(n)方案set判重与“起点判断”的精妙之处3.1 思路来源怎么想到用set做O(1)查找经过暴力解的分析我们现在知道要做两件事一是把查询降到O(1)二是在枚举起点时做剪枝。第一件不说了set天然满足。第二件才是这题的精髓。假设我们已经有了num_set set(nums)现在遍历每一个数字x。怎么知道x是不是一个连续块的左端点答案就是看x - 1在不在num_set里。如果在说明x前面还有“更小的邻居”它不可能是一个块的起点从它开始向后数得到的区间必然不完整而这个区间信息一定已经被更左的那个数字数过了。当且仅当x - 1不在集合里x才是某个连续块真正的最小值才有必要从它开始向后扩展。这个判断看起来简单但它一次性解决了暴力解里的“重复枚举起点”问题。一组数里只有块的左端点会被展开其他数字全部被x - 1 in num_set这个条件拦在外面等于每个块只被处理一次。3.2 核心代码与复杂度推导直接上最优解的完整代码from typing import List 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 num cur_len 1 while cur_num 1 in num_set: cur_num 1 cur_len 1 longest max(longest, cur_len) return longest现在认真算一遍复杂度这是面试必问环节。构造set的循环是O(n)。之后遍历num_set外层for对每个数字做一次num - 1 not in num_set查询这本身是O(1)整体O(n)。关键是while循环的总次数只有“左端点”才能进入while而while每次从当前块里向后找一个“后继数字”。假设整个数组被分成k个连续块第i块长度是len_i那么所有while迭代的次数就是sum(len_i)这个和恰好等于num_set中不重复数字的个数不会超过n。所以总复杂度是O(n) O(n) O(n)也就是O(n)。摊还视角的说法是每个数字在while里被查询的次数不会超过1整体线性。3.3 为什么要遍历num_set而不是遍历原数组第一次写这题的人很容易把for循环写成for num in nums然后发现答案也是对的。确实对绝大多数用例来说两者结果一致但遍历num_set至少有两点好处。第一去重带来的循环次数更少。比如全重复数组[1,1,1,1]遍历nums要处理4次遍历set只处理1次。第二语义更清晰。你现在的核心数据载体已经是集合了逻辑上是“对这些不同数字做区间统计”而不是“对数组每个位置做处理”。代码写给面试官看的时候遍历set也更容易引出“集合天然去重”这个点。还有一个细节容易被忽视num - 1 not in num_set这个查询针对的是集合而不是原数组。如果写成num - 1 not in nums虽然Python里列表in也是合法操作但那是O(n)的线性查找整套代码复杂度直接退化到O(n^2)。3.4 有没有必要用visited集合再做一层标记有人会觉得“只从起点开始数”有点绕于是想用另一种思路遍历数组把每个连续块里的数字都标成visited下次遇到就直接跳过。这种写法也能做到O(n)但需要额外的visited集合代码分支也更多。相比之下num - 1 not in num_set这个“左端点判断”本身就是天然的visited标记。它不需要你显式记录哪些数字已经属于某个块因为每个块的内部数字都会被判断为“非起点”而自动跳过。能用一行判断解决的问题不要整出一套状态管理——这是我在刷题里学到的重要经验。4. 边界条件与易错点我自己踩过和帮别人debug过的坑4.1 空数组、单元素与全重复数组先把结论摆出来空数组返回0单元素返回1全重复数组也返回1。集合解法对这些边界是天然兼容的。空数组set([])为空for循环直接不执行返回0。单元素数组转set后只有1个元素从它开始数找不到后继长度1。全重复数组[1,1,1,1]转set变{1}长度1。不需要任何特判这就是哈希集合解法的优雅之处。相比之下排序解必须处理空数组的nums[0]越界问题多一行防御代码。我之前见过有人在这种边界上画蛇添足看到空数组返回0就特判if not nums: return 0这没问题。但接着又特判if len(nums) 1: return 1这纯属多余。不必要的特判越多出bug的角落越多。4.2 负数与零的兼容性力扣这题的整数可以是负的也可以有0。比如[-1,0,1,2]最长连续序列是[-1,0,1,2]长度4比如[-3,-1,0,1]最长是[-1,0,1]长度3。哈希集合解法对负数没有任何问题num - 1和num 1都是普通整数运算不涉及索引或位序集合里存负数天然支持。排序解也能处理但要注意断点判断写的是nums[i] nums[i - 1] 1这个公式本身和正负号无关。我实际遇到的一个特殊情况是测试用例里出现了10^9级别的大整数。set存大整数没有问题Python整数没有溢出概念可以放心。但这也提醒我不要试图用“数组下标模拟数值范围”那种朴素映射来做这题——如果数字从-10^9到10^9你不可能开一个长度为2*10^9的数组。4.3 Python集合遍历时的隐形坑用Python写这题有一个比较隐蔽的坑跟遍历和修改有关。假如你想在while循环里顺手把已经数过的数字从set里删掉比如写num_set.remove(cur_num)来做剪枝那么恭喜你你会得到一个RuntimeError: Set changed size during iteration。原因很简单你正在遍历num_set同时在遍历过程中修改它Python迭代器会立即罢工。我之前为了“优化”也试过这个写法结果本地跑起来直接报错才意识到这是Python集合的迭代器特性。后来想通了这套算法本身已经保证每个块只展开一次剪枝操作根本不是必要的纯属画蛇添足。如果不死心非要剪枝可以先把set转成list再遍历for num in list(num_set):但这样额外复制了一份空间翻倍不推荐。4.4 重复数字会不会把连续长度算多这一点值得单独拿出来说因为它是我被问过最多的问题。比如nums [0,1,1,2,3]正确答案是[0,1,2,3]的长度4。set(nums)变成{0,1,2,3}重复的1被吸收。外层遍历时0的0-1-1不在集合里0是起点while一路查到3长度4。如果是遍历原数组而非set第一次遇到1时发现1-10在集合里于是跳过第二次遇到1时同样的判断再次成立还是跳过。重复出现的数字在循环里顶多被判断多次但永远无法作为起点展开。所以无论是遍历set还是遍历nums重复数字都不能把长度算多。想通这一点你就不会再担心“去重到底发生在哪一步”了。4.5 内存换时间的代价set的空间开销set(nums)的空间复杂度是O(n)这在算法层面是明确接受的。但我实测过非常大的输入Python set的内存开销确实比数组高不少——底层哈希表除了存元素本身还要存哈希值、指针和冲突链表一个几百万元素的set能把内存吃到上百兆甚至更多。所以刷题阶段空间O(n)没问题但如果在工程里真遇到超大规模数据可以思考是不是要换成外部排序配合分段扫描或者用数据库的窗口函数来求连续区间。LeetCode考的是思维模型落地时还得结合场景做取舍。5. 同类题型串讲与面试答题节奏5.1 与连续递增序列、最长非降子序列的对比刷题不能一道一道孤立地刷最好做完一道就想它的“亲戚题”。和128相关的至少有这三类题目下标是否要求连续数值是否要求连续/有序核心思路128 最长连续序列不要求值必须连续差为1哈希集合 起点判断674 最长连续递增序列要求下标连续值递增即可一次线性扫描300 最长非降子序列LIS不要求下标连续但须保序值非降动态规划 / 贪心二分很多人刷完128之后看到“最长非降子序列非连续”就想着也能用set去重排序搞定这是个很常见的误区。LIS里的“非连续”指的是不要求子序列元素在原始数组里挨着但它要求保序——比如[10,9,2,5,3,7,101,18]的最长非降子序列是[2,3,7,101]它们的位置必须按原数组顺序走不能随便打乱。这和128“只看数值集合不看位置”的语义完全两码事。我建议你把这两个维度拆开看一是下标连不连续二是数值连不连续。两个维度组合下来是四种题型128只占其中一种。把对比表记在心里遇到相似的题目就不会再张冠李戴。5.2 并查集解法另一种线性思路128题还有一个进阶扩展解法——并查集Union-Find。思路是把相邻的数字看作图中的相邻节点每次把x和x1、x-1做union操作最后统计每个连通分量的大小最大值就是答案。并查集实现要维护parent数组和size数组代码量明显更大时间和空间也都是接近线性的。面试时如果你已经流畅给出哈希集合解法面试官一般不要求再写并查集。但如果你能顺口提一句“这题也可以用并查集把所有相邻数字归到同一个连通块最后统计最大块大小”会让面试官觉得你对“等价类/连通分量”的概念有广度。5.3 面试答题的推荐节奏与刷题建议说说我总结的答题节奏照着走基本稳先复述题意确认“值域连续、不要求位置连续”这个核心约束顺便把乱序数组、可能有重复、可能含负数这三个信息点说出来。摆出排序解主动说明它O(nlogn)不满足进阶要求展示你能做复杂度分析。引出哈希集合解set查询O(1)用num - 1 not in num_set判断左端点来剪枝。写代码时强调遍历的是num_set而不是nums并解释为什么。最后用手写的测试用例过一遍逻辑空数组、单元素、重复元素、负数混合。整个过程最好5分钟以内。刷题建议上我做完128之后又去刷了674和300这三题放在一起复盘对“连续”和“保序”这两个概念的理解会非常通透比单纯背题解有用得多。最后分享一个很个人的体会。128题教我的不是哈希表本身而是先定义清楚问题里“连续”到底指什么再动手设计算法。很多看似复杂的算法题卡住人的往往不是代码而是概念没拆解透。我在实际刷题时遇到这类哈希表题目会先在纸上画一两组手写样例把连续块用括号圈出来再想算法。这套思路后来在做工程上的日志数据间断排查、时间区间合并时也用上了。希望你拿到这题时能少走我当初走过的弯路。