企业官网建设流程全解析

说实话，力扣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作为起点，不断检查x+1、x+2……是否在数组里，统计最长长度。如果查询数组用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分支（也就是“遇到断点才结算”），那么当最长连续块恰好延伸到数组末尾时，循环从头到尾没进入过else，max_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-1=0在集合里，于是跳过；第二次遇到1时，同样的判断再次成立，还是跳过。重复出现的数字在循环里顶多被判断多次，但永远无法作为起点展开。

所以无论是遍历set还是遍历nums，重复数字都不能把长度算多。想通这一点，你就不会再担心“去重到底发生在哪一步”了。

4.5 内存换时间的代价：set的空间开销

set(nums)的空间复杂度是O(n)，这在算法层面是明确接受的。但我实测过非常大的输入，Python set的内存开销确实比数组高不少——底层哈希表除了存元素本身，还要存哈希值、指针和冲突链表，一个几百万元素的set能把内存吃到上百兆甚至更多。

所以刷题阶段空间O(n)没问题，但如果在工程里真遇到超大规模数据，可以思考是不是要换成外部排序配合分段扫描，或者用数据库的窗口函数来求连续区间。LeetCode考的是思维模型，落地时还得结合场景做取舍。

5. 同类题型串讲与面试答题节奏

5.1 与连续递增序列、最长非降子序列的对比

刷题不能一道一道孤立地刷，最好做完一道就想它的“亲戚题”。和128相关的至少有这三类：

很多人刷完128之后，看到“最长非降子序列（非连续）”就想着也能用set去重+排序搞定，这是个很常见的误区。LIS里的“非连续”指的是不要求子序列元素在原始数组里挨着，但它要求保序——比如[10,9,2,5,3,7,101,18]的最长非降子序列是[2,3,7,101]，它们的位置必须按原数组顺序走，不能随便打乱。这和128“只看数值集合不看位置”的语义完全两码事。

我建议你把这两个维度拆开看：一是下标连不连续，二是数值连不连续。两个维度组合下来是四种题型，128只占其中一种。把对比表记在心里，遇到相似的题目就不会再张冠李戴。

5.2 并查集解法：另一种线性思路

128题还有一个进阶扩展解法——并查集（Union-Find）。思路是把相邻的数字看作图中的相邻节点，每次把x和x+1、x-1做union操作，最后统计每个连通分量的大小，最大值就是答案。

并查集实现要维护parent数组和size数组，代码量明显更大，时间和空间也都是接近线性的。面试时如果你已经流畅给出哈希集合解法，面试官一般不要求再写并查集。但如果你能顺口提一句“这题也可以用并查集把所有相邻数字归到同一个连通块，最后统计最大块大小”，会让面试官觉得你对“等价类/连通分量”的概念有广度。

5.3 面试答题的推荐节奏与刷题建议

说说我总结的答题节奏，照着走基本稳：

1. 先复述题意，确认“值域连续、不要求位置连续”这个核心约束，顺便把乱序数组、可能有重复、可能含负数这三个信息点说出来。
2. 摆出排序解，主动说明它O(nlogn)不满足进阶要求，展示你能做复杂度分析。
3. 引出哈希集合解：set查询O(1)，用num - 1 not in num_set判断左端点来剪枝。
4. 写代码时强调遍历的是num_set而不是nums，并解释为什么。
5. 最后用手写的测试用例过一遍逻辑：空数组、单元素、重复元素、负数混合。整个过程最好5分钟以内。

刷题建议上，我做完128之后又去刷了674和300，这三题放在一起复盘，对“连续”和“保序”这两个概念的理解会非常通透，比单纯背题解有用得多。

最后分享一个很个人的体会。128题教我的不是哈希表本身，而是先定义清楚问题里“连续”到底指什么，再动手设计算法。很多看似复杂的算法题，卡住人的往往不是代码，而是概念没拆解透。我在实际刷题时，遇到这类哈希表题目会先在纸上画一两组手写样例，把连续块用括号圈出来，再想算法。这套思路后来在做工程上的日志数据间断排查、时间区间合并时也用上了。希望你拿到这题时，能少走我当初走过的弯路。