LeetCode Hot100 刷到第 3 题碰上了 128.最长连续序列。这道题排位很靠前面试频率也很高但说实话我第一次做的时候没觉得它难反而觉得它“有点怪”——明明一个排序就能解决的问题为什么非要整出个 O(n) 的解法后来刷完回头看这道题其实是理解“哈希表怎么参与算法设计”的一个绝佳样本也是 Hot100 里少有的“读题比写题更重要”的题目。这篇就把它彻底拆开从题意到代码到复杂度到易错点一次讲透。1. 先看懂题目在说什么别把“连续”理解成“下标相邻”1.1 一个最容易踩的误区题目给的是一个未排序的整数数组要求找出数字连续的最长序列的长度。注意这里说的是“数字连续”不是“元素在原数组里挨着”。比如[100, 4, 200, 1, 3, 2]最长连续序列是1, 2, 3, 4长度是 4。但你在数组里看这 4 个数下标是 3、5、4、1完全不是连在一起的。也就是说题目要的是“值域上的连续段”不是“下标上的连续段”。这个区别就是整道题的关键。很多人看到“最长连续序列”脑子里第一反应是“排序后扫描一遍数相邻相等的差值”这不能说错因为排序解法确实能算出正确答案而且代码写起来 3 分钟就搞定sort(nums.begin(), nums.end()); int res 0, cur 1; for (int i 1; i nums.size(); i) { if (nums[i] nums[i - 1]) continue; if (nums[i] nums[i - 1] 1) cur; else cur 1; res max(res, cur); }但这道题的要求是 O(n) 时间复杂度排序是 O(n log n)解法本身不达标。我在实际刷题时也见过不少题解直接排序评论区还有人争论“排序也能过啊为什么要 O(n)”。能过样例不代表满足题意面试时面试官追问一句“你知道为什么要求 O(n) 吗”排序解法就露馅了。这也是 Hot100 这类题的考察逻辑它不是在考你会不会写排序而是在考你会不会用哈希表把“查找某个数是否存在”变成 O(1)。1.2 数据规模怎么逼你放弃排序看下约束0 nums.length 10^5数字范围是-10^9 nums[i] 10^9。数据量十万数值跨度却高达 21 亿。如果用布尔数组bool vis[2000000001]来标记每个数字是否存在内存直接爆炸——2e9 个字节是 2GB 起步更不用说还要处理负数偏移。所以这道题天然要求你不开“值域数组”而是用哈希集合来存储元素。这也是为什么官方解法第一行一定是unordered_set或HashSet。我在第一次做这道题时也想过另一个歪门邪道先把数组排序再用哨兵去重本质上还是排序法我就不赘述了。真正能体现这道题价值的是下面要讲的“起点枚举法”它利用了哈希表 O(1) 查找的特性把整体复杂度压到线性。2. 核心思路HashSet 起点起跳为什么能做到 O(n)2.1 “只从序列起点开始数”这句话值多少复杂度经典解法的核心就一句话对于每个数字只有当它没有前驱num - 1不在集合里时才把它当作序列起点然后往右数连续有多少个。反过来看如果num - 1已经在集合里那说明num不可能是某个连续序列的开头直接跳过不用管它。这个“跳过”非常关键。想想看如果不判断num - 1是否存在那对集合里的每个数都要往右扩展。最坏情况比如数组是[1, 2, 3, ..., n]你从 1 数一遍得到 n从 2 数一遍得到 n-1从 3 数一遍得到 n-2……总操作量是 12...n直接 O(n²)。而加上“只有起点才往右数”这个约束后每个数只会被当作起点数一次往右扩展时每个数也只会被“扫过”一次。整体工作量从平方降回线性。拿生活场景打比方你要统计一条街上连续营业的店铺有几家。最笨的办法是每家店都往前数数它前面关了几家、后面开了几家重复劳动一大堆聪明的做法是只看那些“左边邻居没开门”的店从它开始一路数过去这样每家店最多被数一遍。哈希集合在这里扮演的角色就是“快速查左邻右舍是否营业”的通讯录。2.2 代码实现与逐行注释C 版本我写得很保守几乎每一行都可以直接背下来class Solution { public: int longestConsecutive(vectorint nums) { unordered_setint s; for (int x : nums) { s.insert(x); } int ans 0; for (int x : s) { // 只处理序列起点前驱不存在才往下走 if (!s.count(x - 1)) { int cur x; int len 1; while (s.count(cur 1)) { cur; len; } ans max(ans, len); } } return ans; } };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 cur_len 1 while cur 1 in num_set: cur 1 cur_len 1 longest max(longest, cur_len) return longest注意 Python 里我写的是for num in num_set不是for num in nums。这两者结果一样但前者更直接因为集合已经去重遍历时能避免对重复元素发起无意义的起点检查。虽然即使遍历nums整体复杂度依然是 O(n)但遍历去重后的集合在概念上更干净有些题目会在此基础上做变体养成这个习惯有好处。再说一个细节while里面我写的是s.count(cur 1)不是s.find(cur 1) ! s.end()两者都可以。count对unordered_set而言返回值只会是 0 或 1语义明确。C 选手别把它和multiset的count混淆就行。2.3 复杂度推导为什么内层 while 总体是 O(n)这句话是面试重点也是你写完代码后大概率会被追问的问题。需要讲清楚的点是虽然代码里有个嵌套的while看起来像 O(n²)但仔细分析就会发现每个元素只会在它的“起点”那一次被触发内层循环并且每个元素一旦被cur扫过就再也不会被扫第二次。更严谨的推导方式是把每个数字的访问次数拆成两部分一次是外层for在检查它是不是起点时读了它另一次是当它作为某个起点的“后继”时被while读到。一个数字要么自己是起点要么是某个起点的后继不可能又是起点又是后继。所以每个数字最多被读两次。总读取次数不超过 2n时间复杂度 O(n)。哈希集合的查找和插入平均都是 O(1)空间上存储所有不同数字最差也是 O(n)。我刷题时总结过一个话术面试现场这么说最容易让面试官点头“外层循环总共 n 次但内层循环的次数加起来不超过 n因为每个数最多作为某一个连续序列的内部成员被访问一次。整体是线性。” 把这个逻辑理顺比背下代码重要得多。3. 实操过程中的常见问题与排查技巧3.1 问题速查表这道题代码短但实际动手时坑一点都不少。把我踩过的、以及帮别人 review 时看到的问题整理成一张表问题表现原因解决办法空数组或全重复数组返回错误长度忘记处理空集或重复元素空数组时循环不进ans 自然为 0但要确认初始化正确重复元素靠 set 去重不需要单独判断时间复杂度“看似” O(n²)内层 while 从每个元素都发起加if (!s.count(x - 1))只让序列起点进入 while负数、极端大数越界用数组下标存状态改用哈希集合不依赖值域范围数组里有重复数字排序解法容易多算排序后相邻相等没跳过先过掉nums[i] nums[i-1]再判断是否连续while 里死循环条件写反或忘更新cur确保每次循环cur并检查条件是cur 1而不是cur第二行值得单独强调。我第一次提交时就是没写起点判断结果拿[1,2,3,4,5]这种连续大数组一跑循环次数直接爆炸还以为是 LeetCode 测评机卡了。后来打印日志才发现每个数都当起点跑了一遍白白浪费 O(n²)。加一行if (!s.count(x-1))之后瞬间就过了。这个教训我到现在都记得嵌套循环不可怕可怕的是不知道每个元素被访问了几次。3.2 一份“能过样例但可能挂面试”的写法有些写法能通过 LeetCode 的测试用例但面试时暴露问题。比如int longestConsecutive(vectorint nums) { unordered_setint s(nums.begin(), nums.end()); int ans 0; for (int x : nums) { int len 1; while (s.count(x 1)) { x; len; } ans max(ans, len); } return ans; }这段代码在去重后的长连续数组上会退化成 O(n²)因为每个元素都往右扩展了一遍。假如面试官让你分析复杂度你很难自圆其说。更隐蔽的问题是while循环里修改了循环变量x如果后面还要用到原始x逻辑会出错。虽然这个写法在测试机上可能因为数据不强而侥幸 AC但面试时一定要主动改成“仅起点扩展”的规范写法。还有个常见的鬼探头写法是使用mapint, int做动态规划的区间合并比如维护每个连续区间的左右端点长度。这个思路本身没错但代码复杂容易在边界处理上出 bug对这道题来说没必要。面试时优先选择“集合去重 起点枚举”的简洁方案因为可读性最强也最容易解释。4. 通过 Hot100 相邻题建立知识网络4.1 和 994 腐烂的橘子放在一起看“扩散”刷 LeetCode 时我习惯把同类型的题放在一起对比。128 最长连续序列看起来和 994 腐烂的橘子八竿子打不着但往抽象层面看它们都在做“从一个起点开始沿着某种邻接关系一层层扩散”。994 是在二维网格上向上下左右扩散腐烂时间就是 BFS 层数128 是在一维数值上往1方向扩散序列长度就是扩散步数。区别在于 994 用 BFS 是因为网格扩散有“多源同时进行”的需求必须用队列维护轮次128 不用 BFS因为数值链是线性的、单向朝大数方向走一个起点数到底就行不需要分层。这种对比能帮你理解什么时候该上 BFS什么时候单纯用哈希循环就够了。如果你想加深这个印象可以自己写一个新变体如果题目改成“数字可以同时向 1 和 -1 两个方向扩散问覆盖多少个点”那就更像 BFS 了因为它不再是单一起点往一个方向走了而是多个点同时扩张需要队列维护“已经访问过的边界”。这也能解释为什么网上有人会把 128 和图的遍历联系起来。4.2 和 875 爱吃香蕉的狒狒对比何时用二分何时用哈希875 爱吃香蕉的狒狒是 Hot100 里二分答案的经典题给定每小时吃香蕉的速度 k求能在 h 小时内吃完的最小 k。这题有个鲜明的单调性——k 越大耗时越短所以可以在值域上二分。128 最长连续序列则完全不一样它没有任何“可枚举的连续速度区间”你没法说“先猜一个长度再验证是否存在这么长的连续序列”因为验证本身就要 O(n)二分后的验证复杂度不会更好看。这两题放在一起看能帮你建立“什么时候用二分什么时候用哈希”的判断直觉。二分的前提是有单调判定函数而 128 的核心操作是“查某个数在不在集合里”这正是哈希表的强项。我见过不少新手在 128 上硬套二分最后全都折戟原因就是没有意识到问题的操作本质是“存在性查询”而不是“最优化决策”。4.3 和最长非降子序列非连续区分热词里还有一个经典问题最长非降子序列同样带“最长”和“序列”两个词但它特意强调“非连续”即可以在原数组里跳着选元素但选出的元素在数值上不能下降。最典型的是[10, 9, 2, 5, 3, 7, 101, 18]最长递增子序列是[2, 3, 7, 101]长度 4下标是 2、4、5、6不是连着的。这道题和 128 对比一下128 要求值域上连续差值必须为 1但不要求下标连续LIS 要求下标顺序递增但不要求值域连续。也就是说128 的“连续”是数值意义上的连续LIS 的“非连续”是下标意义上的不连续。两者一个查集合一个做 DP/二分方法论完全不同。如果你刷 Hot100 时把这两道题连着做会特别清楚地感受到“读题到底在读什么”。这里再补一个刷题建议不要把热词里的“第1关最长非降子序列(非连续)问题”和 128 混在一起。前者本质是 LIS 变体需要在数组顺序中做动态规划或贪心二分后者只需 HashSet。如果你看到题目描述里出现“原数组顺序”“子序列”这类字样基本可以往 LIS 方向想如果出现“数字连续”“值连续”那大概率是哈希集合题。5. 我的刷题心得这道题教给我的三件事第一读题时一定要区分“下标连续”和“值连续”。这道题最大的坑不是代码难写而是概念混淆。我一开始就默认“连续序列”是下标挨着的硬是在数组上做滑动窗口浪费了一下午。后来重新读题才发现原题里的序列完全可以在数组里散落分布。第二判断复杂度时要看“每个元素被访问了几次”而不是看有几层循环。很多 O(n log n) 甚至 O(n²) 的解法表面都是双层结构真正决定效率的是内层操作触发的条件。这道题的“起点判断”就是一个教科书级的剪枝它让内层 while 的总体执行次数不超过 n。这个分析习惯比背这道题更有用。第三刷题要有“同类对比”的意识。128 和 994、875、LIS 系列放在一起看一个晚上能把哈希、BFS、二分、DP 四种常见套路全串一遍。我是建议大家刷 Hot100 时不要只按编号一个个过而是每刷完几题就想一想“这题和之前哪题有共通点”哪怕只是表面的“扩散”或“连续”都能帮你形成知识网络。最后分享一个我自己常用的自查方法写完 128 后把代码里的if (!s.count(x - 1))这一行注释掉再跑一遍[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]这种数组如果运行时间明显变长说明你已经亲手感受到了 O(n²) 和 O(n) 的差距。这个实验我强烈建议做一次比听任何讲解都直观。