企业官网建设流程全解析

第一次在力扣上刷到“最长连续序列”这道题的时候，我骨子里的第一反应和绝大多数人一模一样：排序，然后从前往后数一遍，答案不就出来了？直到我看见题目要求——时间复杂度得达到 O(n)——才意识到事情没那么简单。这道题是力扣热题 100 的常客，也是很多公司笔试面试的经典考题：给定一个未排序的整数数组，找出数字连续的最长序列的长度。看起来只是道“小题目”，卡住的人却不少，因为它真正考的不是“你会不会排序”，而是你能不能跳出“有序”这个思维定式。

这篇文章想做的事情很朴素：把这道题从直觉误区、核心原理、代码实现到复杂度论证，一层层拆开讲透。无论你是刚开始刷题的小白，还是已经会写解法、但一直说不清“两层循环为什么是 O(n)”的老手，应该都能从里面拿到一点实在的东西。

1. 第一直觉为什么会被卡住：排序法的 O(n log n) 陷阱

1.1 排序确实能解，但代价并不便宜

先看大多数人第一时间的思路。把数组排好序，再从头到尾扫一遍，挨个检查相邻两个数的差是否为 1，顺便维护一个当前连续长度和一个全局最大长度，整个过程非常自然。代码写出来大概是这种感觉：

def longest_consecutive_sort(nums): if not nums: return 0 nums.sort() length = 1 best = 1 for i in range(1, len(nums)): if nums[i] == nums[i - 1]: continue if nums[i] == nums[i - 1] + 1: length += 1 else: length = 1 best = max(best, length) return best

这段代码能跑，也能通过不少测试用例，但它违背了题目的底线要求：排序算法的时间复杂度最好也就是 O(n log n)，而题目明确要 O(n)。很多人第一眼会觉得“这不是鸡蛋里挑骨头吗，排序多快啊”，但你要知道，当 n 到千万级别时，n log n 比 n 多出来的计算量不是一两倍，而是数十倍。题目的意思很直接：不允许你对整个数组做全局排序，必须想别的办法。

1.2 这里的“连续”到底在说什么

我们退一步想：什么叫做“数字连续”？在 [1, 2, 3, 4] 里，1、2、3、4 是连续的。在 [8, 1, 9, 3, 2, 0, 7] 这个乱序数组里，0、1、2、3 也是一段连续序列，长度是 4；7、8、9 是另一段，长度是 3。

这个观察非常关键：连续关系并不依赖数组的物理顺序，而是“集合里存在哪些相邻数字”决定的。你要判断 2 后面有没有 3，不需要数组有序，只需要能快速回答一个问题：“3 在不在这个集合里？”

如果能做到 O(1) 地回答这种“存不存在”的问题，那么判断连续就不再需要把整个数组排一遍了，只需要沿着邻居关系一条路走下去就行。这就是这道题破局的第一个核心念头。

2. 换一种思路：从“连续段的开头”数起，而不是从每个元素数起

2.1 用哈希集合建立 O(1) 的邻居查询

既然要反复查询“某个数在不在”，最合适的容器就是哈希集合。Python 的 set、Java 的 HashSet、C++ 的 unordered_set，平均复杂度都能做到 O(1) 的插入和查询。第一步永远是去重并建集合：

num_set = set(nums)

这一步做完以后，数组里有多少个元素不重要了，重要的是“有哪些不同的数”。任何一个数 num，只要 num + 1 在集合里，它们就是相邻的连续关系。这个查询不需要排序，不需要二分，就是一次哈希查找。

2.2 关键判断：num - 1 在不在集合里

现在进入整道题最容易被忽略、也最精髓的一步。假设集合里有 [1, 2, 3]，如果我们遍历集合里的每一个数，都从它自己开始往右数，会发生什么？

• 从 1 开始数：1、2、3，长度 3
• 从 2 开始数：2、3，长度 2
• 从 3 开始数：3，长度 1

1 被数了三次，2 被数了两次，3 被数了一次。虽然最后答案还是 3，但中间做了大量重复工作。如果数组很长，这种重复会让复杂度像滚雪球一样涨上去。

怎么避免重复？规则其实很简单：只从一段连续序列的最左边开始数。判断方法就是看 num - 1 是否存在于集合中：

• 如果 num - 1 不在集合里，说明 num 左边没有邻居，它一定是某一段连续序列的起点，这时候才值得从它开始往后数。
• 如果 num - 1 在集合里，说明 num 是某一段的中间元素或右端元素，它肯定会更左边的那个起点数到，所以直接跳过它。

用前面那个例子：[8, 1, 9, 3, 2, 0, 7] 建出的集合是 {0, 1, 2, 3, 7, 8, 9}。遍历集合：

• 0 的左边是 -1，不在集合里，0 是起点。从 0 开始数：0、1、2、3，长度 4。
• 1 的左边是 0，在集合里，跳过。
• 2 的左边是 1，在集合里，跳过。
• 3 的左边是 2，在集合里，跳过。
• 7 的左边是 6，不在集合里，7 是起点。从 7 开始数：7、8、9，长度 3。
• 8、9 左边都在集合里，跳过。

最长长度是 4，答案正确，而且每个元素最多只会被“从起点开始数的那一次”覆盖到，没有重复劳动。

2.3 用生活里的场景来类比

可以把每个连续段想成一队人按编号站好，但所有人是乱序站在操场上的。要知道最长的一队有多长，你不需要让所有人按编号重新排队，只需要找到每一队的“队头”——也就是左边没有队友的那个人——然后沿着队伍往后数人头。

这样做的妙处在于：每个人都只属于一支队伍，也只被数一次。你在考察“谁是队头”的时候花了一点时间，但一旦确认了队头，数完整支队伍就有了全部信息，中间的队员完全不用重复动。这就是整道题能在 O(n) 时间内完成的直觉来源。

3. 一套能直接跑的代码：完整实现与逐行拆解

3.1 Python 版本，短但每一行都有讲究

把上面的思想落成代码，Python 版本尤其简洁：

def longest_consecutive(nums): 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

这里有一个非常容易忽略的细节：for 循环遍历的是num_set而不是原始的nums。为什么？

因为 set 已经把重复元素去掉了一份。如果你遍历原始数组，遇到一个重复的起点值，比如数组里有三个 1，而 1 刚好是一个连续段的起点，那么 while 循环就会把整段连续序列从头到尾数三遍。虽然答案还是对的，但做了大量无用功。遍历 set 之后，每个不同的数字只被处理一次，思路也更干净。

再逐行看核心逻辑：

• if num - 1 not in num_set：判断当前数是不是一个连续段的左端点。这一步是整个算法的心脏。
• while cur + 1 in num_set：从起点开始不断向右试探，看看有没有下一个数。只要存在，就继续走下去。
• longest = max(longest, length)：每找到一段就更新一次全局最长长度。

有些写法会把length = 1和cur = num放在 if 外面，那样也能跑，但对不是起点的数字也会进入 while 循环，做的全是重复劳动。正确做法是把 while 放进 if 内部，把力气只花在起点上。

3.2 Java 和 C++ 的写法，思路完全一致

很多面试官喜欢让你写 Java 或 C++，核心逻辑不变，只是容器和语法换了。

public int longestConsecutive(int[] nums) { Set<Integer> set = new HashSet<>(); for (int x : nums) { set.add(x); } int best = 0; for (int x : set) { if (!set.contains(x - 1)) { int cur = x; int len = 1; while (set.contains(cur + 1)) { cur++; len++; } best = Math.max(best, len); } } return best; }

C++ 则是把Set<Integer>换成unordered_set<int>，其余结构基本不变。语言差异在这个层面其实无关紧要，重要的是你脑子里有没有“只从起点开始数”这个模型。很多同学在面试时一紧张就开始套模板，把 HashSet 建好之后就想当然地对每个元素做 while，结果代码看起来也像模像样，但一旦被追问“为什么这个两层循环是 O(n)”，就支支吾吾说不清楚。这个问题我们马上展开讲。

4. 两层循环为什么仍然是 O(n)：摊还代价的真实来源

4.1 最典型的质疑：外层 for 套内层 while，难道不是 O(n²)？

这是评论区出现频率最高的问题。表面看你有一个外层 for 遍历所有元素，还有一个内层 while 在里面不断往后查，许多人第一反应就是最坏情况下 O(n²)。这个质疑非常合理，因为如果内层 while 对于每个起点都要把剩余元素全部数一遍，那复杂度就爆了。

但事实是：内层 while 的所有迭代次数加起来，最多不会超过 n 次。这个结论才是真正的题眼。

为什么？因为一个元素一旦被某次 while 循环“数到了”，它就被消耗掉了。它已经作为某个连续段的一部分被计入长度，不会再有第二个起点去数它。拿前面 [0, 1, 2, 3, 7, 8, 9] 的例子来说，0 起点的 while 把 1、2、3 都数了一遍，等遍历到 1、2、3 时，它们因为num - 1在集合里而被跳过，根本不会进入新的 while。

换句话说，每个元素最多扮演两种角色：要么因为左边没有邻居而成为起点，要么作为某个起点往后数的时候被访问一次。这两种角色都不会重复。外层 for 每个元素做一次检查，总共 n 次；内层 while 所有循环加起来最多把每个元素作为“被访问者”处理一次，也是 n 次上下。整体操作次数大致就是 2n 到 3n 的级别，这就是 O(n)。

专业一点的说法叫“摊还分析”。你不需要把每一次 while 单独拉出来计算最坏情况，而是看整个算法在执行过程中所有内层迭代的总量。内层迭代的总量被一个数学上限卡住——它不可能超过集合的大小。所以哪怕循环嵌套在一起，整体复杂度依然是线性的。

4.2 为什么哈希集合查询是 O(1) 平均

这里还需要一个前提：哈希集合的查找平均是 O(1)。底层原理是哈希函数把元素映射到数组桶里，大多数情况下一次就能找到或确认不存在。当然，极端哈希冲突或恶意构造数据时可能会退化，但在算法题的评测环境下，可以将其视为常数时间操作。这里有一个值得记住的点：面试里说 O(n) 时，其实默认了哈希操作为平均 O(1)。如果面试官非要追问最坏情况，你可以补充一句“如果要求严格的最坏情况 O(n)，需要换更复杂的数据结构”，一般说到这里就够了。

4.3 空间换时间，值得吗

这个解法用了一个 HashSet，最坏情况下空间是 O(n)。如果数组里全部是不重复的元素，那集合大小就是 n。相比排序解法可能只需要 O(log n) 的额外空间，这个方案的空间代价确实更高，但换来了时间上的大优势。

在多数场景下，这个交换是划算的，尤其是当你面对的是“一次查询、数据量很大、内存尚可”的情况。这也是为什么题目明确允许你使用额外空间来换时间。空间换时间在工程中也极其常见，比如缓存、索引，本质上都是同一个道理。

5. 实战中容易翻车的细节：边界条件、错误写法与替代方案

5.1 负数和 0 不是特殊分子

很多人写代码时头脑里默认数字都是从 1 开始的，结果测试用例里出现[-1, 0, 1]或[-5]就懵了。其实哈希集合对整数类型一视同仁，负数、0、正数处理方式完全一致。num - 1 not in num_set这个判断对负数同样成立。比如集合是 {-1, 0, 1}，-1 的左边是 -2，不在集合里，于是 -1 作为起点向后数出长度 3，答案正确。

唯一要注意的是初始化变量。longest = 0是一个稳妥的初始值，因为空数组也应该返回 0。如果把longest初始化为 1，遇到空数组就会出错，需要额外写 if 判断。

5.2 空数组和单元素数组最容易出低级错误

空数组返回 0，单元素数组返回 1。这两个边界看起来人畜无害，但很多时候是提交之后才发现翻车。用set(nums)建集合之后，空集自然进不了 for 循环，longest保持 0，单元素集合进去算一遍，长度为 1，结果也正确。这也是我推荐把longest初始化为 0 而不是 1 的原因，初始值选对了，边界分支就不用单独处理。

5.3 重复元素是来帮忙的，不是来添乱的

数组里出现重复的数字，比如 [0, 1, 1, 2, 2, 3]，并不会让最长连续序列变长，因为连续长度数的是“不同的数字”是否相邻，而不是同一个数字出现多少次。对原始数组做排序遍历时，重复值会引入额外的去重判断，代码里往往要加continue分支；而 set 天然帮你完成了去重，这反而是写起来更舒服的地方。

注意：如果用我前面提到的“遍历原始数组”的错误版本，重复数字还可能导致同一个连续段被重复数多次。所以一定要遍历 set，而不是遍历原始数组。

5.4 如果题目改成“返回最长区间的左右端点”

面试官经常会追加一个问题：只返回长度不够，你能否把最长的那一段的左端点和右端点也返回？改起来非常自然。在 while 循环结束之后，num是这段的起点，cur是这段的终点，把它们记录到一个变量里，最后和最长长度一起更新就行。这说明算法的骨架没有变，变的只是你在扫描过程中多记了两个值。

5.5 还有哪些替代方案可以做到 O(n)

除了 HashSet 思路，也存在其他线性解法，但它们要么更复杂，要么有额外限制，了解即可。

第一个是“DFS + 记忆化”。你可以把每个数字看作一个节点，数字之间相差 1 的关系看作边，那么问题变成了“无向图中最长路径的长度”。对每个未访问的数字做深度优先搜索，记录访问过的节点，整体也是 O(n)。不过这种做法在纯数组的一维场景下显得有些重，更适合二维网格等变体。

第二个是“并查集”。把相邻的数字合并到同一个集合里，最后统计每个集合的大小。并查集的路径压缩和按秩合并可以做到近似 O(n)，但代码量明显更大，也不如 HashSet 解法直观。

第三类是用数组或位图代替集合。如果题目给出了数据范围，比如数字都在 [0, 1000] 之间，用一个布尔数组就能完成同样的查询，而且常数更小。但数字范围一旦变大或者出现负数，这种方案就不通用了。综合来看，HashSet 思路是普适性最好、最容易在面试白板上讲清楚的解法。

5.6 用排序方案在工程上并不丢人

最后说一个可能有点反直觉的观点：如果这不是算法题，而是真实项目里的一段需求，我大概率会先考虑排序。原因很简单，真实数据规模通常可控，数组排序的常数开销很小，而且代码可读性好、不容易出错。O(n) 解法的哈希操作虽然理论上是线性，但常数可能并不小，内存访问也不像连续数组那样缓存友好。

所以不要觉得“不用 O(n) 就低人一等”。算法题的约束是为了训练思维，工程里的取舍则是另一门学问。你在面试时能主动说出这一点，反而会让面试官觉得你不只是一个会背题的人。

6. 从这道题延伸出去：变体、追问与实际应用

6.1 面试官常见的追问方式

围绕这道题，面试官大概率不会只满足于“你写出来了”，而是会追问一些更本质的问题。

比如他会问：为什么不能用排序？这个问题的标准答案不是“排序慢”，而是“排序的复杂度下界是 O(n log n)，不满足题目对 O(n) 的要求”。如果再深挖，他会问：为什么哈希查询能算 O(1)？这时候你要不慌不忙地解释哈希表的桶、哈希冲突和平均复杂度。还有的面试官会问：如果内存限制很严格，只允许 O(1) 额外空间怎么办？这个问题的答案其实很残酷——在无序且范围不定的整数数组里，很难再做到 O(n) 时间加 O(1) 空间，要么接受 O(n log n) 的排序，要么接受其他约束。面试官想听的其实是“你能说出这个 trade-off”。

6.2 二维变体和同类型题目

把一维的“相邻关系”换成二维的“上下左右相邻”，就成了另一类经典问题，比如网格里的岛屿数量、最大岛屿面积。核心观察完全一致：你不必对所有格点重复遍历，只需要找到“起点”，然后沿着相邻关系把一整块区域一次走完，走过的格子标记为已访问，避免重复劳动。

理解了这一点，你再去做类似的二维连通性问题时，会觉得它们的骨架其实是同一个：用某种结构存储元素，用 O(1) 的方式查询邻居，从每一块的种子开始遍历，并且保证每个元素只被遍历一次。这种“遍历一次”的思维方式，比背下来的 DFS 模板值钱得多。

6.3 真实场景里哪里会用到

现实世界中真的有和这道题同构的问题。举几个例子：

• 服务器日志里有一串请求 ID，由于系统抖动可能丢失一部分，你想找出最长的一段连续 ID，用来判断故障影响范围。
• 游戏后台统计玩家登录记录，给你一堆日期，要计算最长连续登录天数。把日期转成时间戳之后，本质上就是找最长连续序列。
• 数据库分配自增主键后，某段时间出现回滚或删除，你想知道当前连续可用的主键区间有多长。

这些场景和刷题之间当然有差距，因为真实数据往往已经有某种顺序或索引，但核心的数据结构思路是通用的：把无序的东西放进一个能快速查询“邻居是否存在”的容器里，然后只从起点的位置开始遍历。这套思路不只属于力扣第 128 题。

6.4 我个人在刷这道题时的三个习惯

每次讲这道题，我都会提醒自己和身边的人养成三个小习惯。

第一，写完代码后先检查遍历的容器。如果你遍历的是原始数组而不是 set，先停下来想想重复元素会造成什么影响。这一点看似微小，却在很多人的真实代码中出现过。

第二，习惯性地在脑中补一个负数用例。很多人测试的时候习惯输入 [1, 2, 3] 这种漂亮的正数数组，做了多余的验证。真正容易出错的往往是[-1, 0, 1]、[100, 4, 200, 1, 3, 2]、[]、[0]这种包含边界值的用例。

第三，把复杂度论证练到能脱口而出的程度。不要满足于“我的代码跑过了几百个测试用例”，要能解释清楚为什么外循环和内循环加起来是线性扫描。面试中“能写”和“能讲明白”是两种水平，这道题的分水岭恰好就在这个解释上。

最后再分享一个我自己的小技巧：遇到类似“无序数组里找某种结构”的题，我会先问自己三个问题——能不能用集合去重？能不能用 O(1) 查询邻居？能不能保证每个元素只被处理一次？这三个问题想明白，很多题就不再是背模板的问题，而是变成了一种顺理成章的推导。