企业官网建设流程全解析

128 题，最长连续序列。这个编号只要刷过一段时间在线题库就不会陌生，标的难度是中等，但不少人在它身上卡过壳。题目一句话就能说清：给定一个无序整数数组，找出数字连续的最长序列的长度，并且要求时间复杂度控制在 O(n)。这里的连续，指的是值连续，1、2、3、4 这样才算，跟这些数字在数组里站没站在一起没有任何关系。

看起来像个送分题，真正动手就会发现：排序的思路一两行就能写完，但 O(n log n) 达不到要求；暴力双层循环能解，但最坏情况直接超时；哪怕想到了哈希集合，落地时也容易在“什么时候才需要向后延伸计数”这个问题上绕进去。这篇文章我想结合自己刷题、改 bug、面试别人和写工程代码时的经验，把这道题从题意、复杂度分析到三种主流解法完整拆一遍，再把面试里高频的追问和真实项目里的相似场景一并梳理清楚。适合正在准备算法面试的开发者，也适合想补一补哈希巧用思路、想搞清楚“空间换时间”到底怎么落地的人。

1. 先把题意掰开揉碎：连续序列到底指什么

1.1 一个例子讲清题目要求

先看最经典的例子。输入数组是[100, 4, 200, 1, 3, 2]，答案是多少？是 4。因为数组里存在 1、2、3、4 这 4 个连续值，所以最长连续序列长度是 4。

这里有三个关键字值得圈出来：第一是“无序”，题目没有保证元素有序，甚至故意给你一个乱序的数组；第二是“连续”，指值连续，也就是相邻两个数相差 1；第三是“序列长度”，它不要求这些数字在原数组中挨在一起，只要值存在，就能串成连续序列。

这跟很多人在初学时脑子里的“最长连续递增子数组”是完全不同的概念。子数组要求位置连续，比如[1, 2, 5, 3, 4]里的5, 3就不能靠位置连续参与计数。但本题是“值连续”，1、3、4 虽然位置分散，只要在集合中同时存在，就能组成连续段的一部分。理解这个区别，是避免后面所有混乱的前提。

1.2 三个最容易踩的坑

第一个坑，是把“连续序列”理解成“原数组里连续出现”。这一点在上面已经点过，但确实是最常见的误解。很多人拿到题第一反应是“滑动窗口”，然后发现窗口怎么滑都不对，因为数字在原数组里是乱序的，窗口根本框不住连续值。其实只要把“存在性”作为判断标准，思路马上就转到哈希上去了。

第二个坑，是忽略重复元素。比如输入[0, 0, 1, 2]，正确答案是 3，因为 0、1、2 能组成长度为 3 的连续序列，另一个 0 是多余的重复元素。如果把数组直接放进哈希集合，重复值自动被去重，不影响结果；但如果用排序后遍历的方式，记得跳过重复元素，不然会重复计数。这个细节在面试现场最容易出 bug。

第三个坑，是边界条件。空数组应该返回 0，只有一个元素的数组应该返回 1。这两个特判本身不难，难的是很多人写主逻辑的时候把返回初始值设错，比如把最长长度初始化为 1，空数组就直接崩了。我一般建议养成习惯：看到数组类题目，先看一眼入参可能是空、可能是单元素、可能全是相同值，在脑内跑一遍边界再动手。

1.3 题目的隐藏考点

很多人以为这道题考的是“会不会用哈希表”，其实考的是两件事。第一是复杂度意识：能不能快速意识到排序在 O(n) 的限制下不可行；第二是哈希的“存在性查询”能力：把数组转成集合之后，x是否出现过就变成了 O(1) 的操作，整个算法的瓶颈从数据规模转移到了逻辑设计上。

还有一个隐藏考点是“如何避免重复计算”。如果无脑对每个元素都向后延伸计数，比如碰到 1 数一遍 1、2、3、4，碰到 2 又数一遍 2、3、4，最坏情况会退化成 O(n²)。题目的精髓就在于找到一种方法，让每个连续区间只被计数一次。这个“一次”怎么做到，就是接下来要重点讲的核心。

2. 为什么排序不是答案：复杂度分析才是突破口

2.1 排序思路和它的代价

拿到这道题，绝大多数人的第一直觉都是排序。思路非常简单：先从小到大排个序，然后遍历数组，如果当前数字等于前一个数字加 1，就对计数器加 1；如果断了，就重置计数器；最后取计数器历史最大值。代码写起来不到二十行，逻辑也直白。

问题出在复杂度。排序本身的时间复杂度，基于比较的经典排序算法是 O(n log n)，这才刚刚开始，后面的线性遍历又要 O(n)。整体复杂度由排序主导，是 O(n log n)，题目明确要求 O(n)。不管用快排、归并还是堆排序，只要是基于比较的排序，都突破不了这个天花板。所以排序这条路，在算法要求面前直接出局。

这个时候有些同学会想：用计数排序或者桶排序不就能到 O(n) 了吗？理论上可以，但前提是知道数据的值域范围。如果题目说的是整数，没说范围，那值域可能是稀疏且跨度巨大的，开一个max - min + 1大小的数组纯粹是灾难。所以通用解法不能依赖这种特殊假设，这也是正规题解里几乎没人提桶排序的原因。

2.2 O(n) 要求的真正含义

O(n) 意味着什么？意味着你从头到尾把每个元素看几遍都可以，只要总次数是线性的，但你不能做任何嵌套的、对整个数据集规模的重复扫描。排序是全局重排，O(n log n)，直接超标；双层循环对每个元素都往后找，O(n²)，更超标。

那什么操作可以做到 O(1)？哈希集合的查找。把 n 个元素放进集合，构建集合需要 O(n)，之后每次查“某个值在不在集合里”平均只要 O(1)。这个基本操作是整个解法的地基。我习惯把这种题看成一道算术题：用 O(n) 的建集合成本，换来 n 次 O(1) 查询，总成本还是 O(n)。关键就是，不能再对每个元素都做一整条链式的查找，必须让每个元素只属于某一次计数。

这里有一个很重要的思维转换：从“对数组做处理”换成“对集合做查询”。数组强调顺序和位置，集合强调存在与归属。直觉上，连续序列的长短不依赖元素位置，所以集合这个抽象层次反而更贴近问题本质。这也是为什么几乎所有正解第一步都是num_set = set(nums)。

2.3 空间换时间：哈希结构带来的转机

排序思路输在时间上，而哈希解法本质上是拿空间换时间。多花 O(n) 的空间建一个集合，换来所有后续查找的 O(1) 时间。这类交换在算法题里太常见了，但很多人只在做题时用到它，一到工程里就忘了。

举个现实中的例子，你有一份用户签到日志，想知道最长连续签到天数。最笨的办法是每天去数据库里查一次，查 n 次；好一点的办法是基于日期字段排序，然后线性扫一遍。但在数据量很大的场景下，排序可能很贵。如果把所有签到日期读到一个哈希集合里，再从那批日期的起点出发做连续判断，查询次数大幅下降。说白了，哈希集合在这里干的事情就是把“是否存在”这个高频问题变成 O(1) 查询，这正是那道算法题在现实世界里的原型。

3. 哈希集合解法：一次遍历的核心技巧

3.1 为什么必须判断 num - 1

哈希集合解法的核心只有两句话：遍历集合中的每个数字，如果num - 1不在集合中，说明num是一段连续序列的起点；从起点开始，不断地检查num + 1是否在集合中，边检查边计数。

为什么要先判断num - 1？这是整道题最关键、也最容易被忽略的一个步骤。如果不做这个判断，而是对每个元素都向后数，会有一大批元素反复进入同一条计数链。举个例子，数组是[1, 2, 3, 4]，遍历到 1 时数出长度 4，遍历到 2 时又会数出长度 3，遍历到 3 数出长度 2，总操作量成了等差数列求和，复杂度退化成 O(n²)。

如果先判断num - 1是否在集合里，情况完全不一样：1 的num - 1 = 0不在集合中，1 是起点，从 1 延伸到 4，数出长度 4；2 的num - 1 = 1在集合中，说明 2 不是起点，跳过；3、4 同样跳过。最终每个连续区间只有它的最小值会触发一次完整计数，区间内其他元素都只做了一次num - 1存在性判断。总工作量是 O(n + n)，仍然是 O(n)。

这个思路我想打一个比方：一段连续序列就像一根绳子，你只需要抓住绳子的最左端往外拉，就能量出整根绳子的长度；如果每一节都抓一遍往外拉，就重复量了很多次。num - 1的判断，就是在帮你确认“我抓到的是不是最左端”。

3.2 完整代码与执行过程演示

Python 的实现非常简洁：

def longestConsecutive(nums): num_set = set(nums) longest = 0 for num in num_set: # 只有 num - 1 不存在，num 才是连续序列的起点 if num - 1 not in num_set: current_num = num current_len = 1 # 从起点向后延伸，统计长度 while current_num + 1 in num_set: current_num += 1 current_len += 1 longest = max(longest, current_len) return longest

拿[100, 4, 200, 1, 3, 2]手动跑一遍。先去重得到集合{1, 2, 3, 4, 100, 200}。遍历到 100，99不在集合中，起点成立，但101不在，所以当前长度 1，longest 变成 1。遍历到 4，3在集合中，跳过。遍历到 200，199不在，起点成立，201不在，长度 1，longest 还是 1。遍历到 1，0不在集合中，起点成立，从 1 查到 2、3、4，当前长度 4，longest 更新为 4。遍历到 3 和 2，前驱都在集合中，跳过。最后返回 4。

整个过程只有1触发了一次完整的 while 循环，其他元素都是 O(1) 的直接判断。这就是算法高效的核心原因。

3.3 复杂度与正确性分析

时间复杂度是严格 O(n) 吗？是的，但要理解为什么。每个数字在最外层的for循环里都会访问一次，这个是 O(n)。真正进入while循环的次数，取决于这个数字是不是某个连续段的最小值。而一个数字一旦在while里被访问，它永远不会再作为某个更长序列的后继被访问第二次，因为那段序列从它的前驱最小值开始就已经把它数过了。同一段连续区间只有最小值能打开 while，其他值都因为前驱存在而被跳过。所以 while 内部所有元素被访问的总次数也是 O(n)。合起来是 O(n)。

空间复杂度是 O(n)，因为创建了与数组规模等价的哈希集合。这里用到一个细节：去重后的集合大小小于等于原数组长度，重复元素的场景下空间更省。但复杂度量级不改变，仍记 O(n)。

这个解法的正确性可以从数学上简单论证：任何一个连续序列[x, x+1, ..., y]，它的最小值x一定满足x - 1不在集合中，所以必然会作为起点被遍历到；从x出发的 while 循环会一直延伸到y，正好把该序列的长度统计出来。不会遗漏，也不会重复。这也是为什么这个解法既高效又直观。

4. 同一道题的三条路：动态规划与并查集

4.1 哈希表记录区间端点的解法

哈希集合解法之外，还有另一种也很有意思的实现：用哈希表记录“某个值作为区间端点时，所在连续区间的长度”。每来一个新数字num，看它的邻居num - 1和num + 1是否已经在表里。如果左边有长度left，右边有长度right，那么把num放入中间后，新区间的长度就是left + right + 1。

难点在于更新后要保证区间两个端点处的哈希值也同步更新，因为只有端点的长度信息在将来拼接时有用。中间那些数字的长度值不会再被使用，更新它们纯属浪费。

代码是这样的：

def longestConsecutive(nums): length_map = {} longest = 0 for num in nums: if num in length_map: continue left = length_map.get(num - 1, 0) right = length_map.get(num + 1, 0) cur_len = left + right + 1 length_map[num] = cur_len longest = max(longest, cur_len) # 只更新连续区间的两个端点 length_map[num - left] = cur_len length_map[num + right] = cur_len return longest

这种写法的时间复杂度同样是 O(n)，空间 O(n)。它的好处是不需要在代码里显式地做 while 向后搜索，而是把“长度”直接缓存在端点位置，适合需要快速查询某个数所在区间长度的场景。缺点是比较绕，尤其是端点更新的那两行，不少人写错成把区间内所有值都更新一遍，结果每次都 O(n)，整体退化成 O(n²)。

4.2 并查集解法

还有一种思路是用并查集。把每个数字看作一个节点，如果num + 1也存在，就把num和num + 1合并到同一个集合里。并查集里每个集合的 size 就代表一段连续序列的长度，最终返回最大 size。

class UnionFind: def __init__(self, nums): unique_nums = set(nums) self.parent = {x: x for x in unique_nums} self.size = {x: 1 for x in unique_nums} def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) # 路径压缩 return self.parent[x] def union(self, x, y): if y not in self.parent: return root_x = self.find(x) root_y = self.find(y) if root_x == root_y: return # 按树大小合并，让小树并到大树上 if self.size[root_x] < self.size[root_y]: root_x, root_y = root_y, root_x self.parent[root_y] = root_x self.size[root_x] += self.size[root_y] def longestConsecutive(nums): if not nums: return 0 uf = UnionFind(nums) for num in nums: if num + 1 in uf.parent: uf.union(num, num + 1) return max(uf.size.values())

这段代码里有个细节，初始化并查集时要先去重，否则多余元素会出现parent里已有键值的情况，并查集内部处理起来容易混乱。同时，使用num + 1进行合并，保证了连续关系只向右延伸，不会出现向左、向右都合并造成环的问题。

并查集解法的均摊时间复杂度接近 O(n)，空间 O(n)，但实际运行常数比哈希集合解法大一些，代码量也明显更多。它在面试中不是一个很讨巧的选择，因为手写并查集本身就容易出错，还要处理路径压缩和按秩合并。但它是一个很好的知识广度展示：如果你能主动提出并查集解法，面试官会下意识觉得你对常见数据结构掌握得比较全面。

4.3 三种解法对比与适用场景

三种解法放在一起看，各有各的定位。

在实际编码和面试中，我首选哈希集合法。理由很简单：最容易写对，最难出 bug，而且思路跟面试官解释起来非常顺畅。哈希表端点法适合作为拓展方案和面试官聊，展示你还能从另一端切入。并查集则属于加分项，可以用来讨论“如果这个连续区间还要维护额外信息，比如区间里的最大值、最小值，并查集会更好扩展”。

5. 从面试到工程：变体、追问与实战启发

5.1 常见变体与扩展思路

这道题有几个高频变体，几乎每一个都值得刷一遍。

第一个变体是要求输出具体的最长连续序列，而不仅仅是长度。这个改动让哈希集合法仍然适用：在确认起点后，while 延伸时把每个值收集到列表里，最后输出长度最长的那个区间。需要注意，如果存在多个相同长度的区间，题目一般没有强制要求输出哪一个，但面试官可能随口问一句“如果要全部输出呢”，这时候复杂度就要重新讨论了。

第二个变体是数据会持续流入，要求实时维护当前所有数字中最长连续序列的长度。这时哈希集合法就显得不便，因为每次插入一个新数字后，我们希望能立刻知道新旧序列的合并结果。哈希表端点法在这里明显更好用：它天然支持增量更新，新数字到来时看看左右端点长度，马上就能得到最新合并后的长度。

第三个变体是二维甚至多维的连续路径。比如在一个棋盘上，找最长的“上下左右连续递增路径”，那就是另外一道经典题了，往往需要配合记忆化搜索。虽然结构和一维版本差异很大，但骨子里还是在找“连续”与“最长”这两个概念的组合，设计思路是可以互相借鉴的。

5.2 面试官最常追问的两个问题

面试官对这道题最常见的追加提问，第一个是：“如果数据量非常大，内存放不下整个哈希集合，怎么办？”这是一个信号题，考察你在工程上能不能跳出标准答案。常规思路是想办法分段处理或者用外排序，但有一个更巧的方案：采用布隆过滤器之类的概率型结构来近似判断“某个数是否存在”。代价是可能产生误判，但能省下大量内存。现实中，如果数据分布在多台机器上，还要设计分区规则，尽量让相近的数字落在同一个分区，然后再用哈希集合求解。

第二个常见追问是：“把数组改成可能有重复元素，结果有影响吗？”标准回答是：没影响，因为连续序列关心的是“值是否存在”，而不是出现了几次。重复值被集合天然去重。如果面试官再深一层，问“那如果要求每个数字在原数组中的出现次数也计入长度，怎么改？”这就变成另一个问题了，需要统计频率而不是单纯的存在性。

还有一个我遇到过的追问是：“为什么 while 循环里用的是current_num + 1，而不是num + 1？”这个问题看似简单，其实是在考察你有没有真正理解“向后延伸”的含义。如果一直用num + 1，判断的就是起点旁边的第二个数在不在，而不是逐段往后走，计数就完全错了。能对答如流的话，面试官基本就会放过这道题了。

5.3 这类思维在真实工程里的落点

不要觉得这道题只是面试场上的八股，它的思想在工程项目里能找到许多影子。

我维护过一套用户行为分析系统，里面有一张“用户连续签到天数”的需求。最开始的实现是每天开个任务扫全表，然后排序、比较相邻日期，性能和正确性都不稳定。后来我把需求抽象了一下，发现本质上就是找“用户签到日期集合”的最大连续长度。先把日期字符串转成时间戳放进哈希集合，然后对每个用户只从连续区间的起点开始数，逻辑跟 128 题几乎一模一样，只是把数字换成了日期。效率提升非常明显，因为省去了大量重复扫描和全局排序。

另一个落点是在日志分析中，判断一批服务器的可用时间段。将服务器在线时间点组成集合之后，最长的连续在线时段同样可以用这类算法在内存里 O(n) 算出来。工程实现的难点大多不在算法本身，而在于把时间戳、节假日、时区这些现实因素清洗干净。清洗之后，核心逻辑往往就是哈希集合加连续判断这个骨架。

所以我的经验是，遇到一个“元素存在性判断特高频”的场景，都可以先想想哈希集合能不能解决一部分问题。它不是一个万能模板，但确实是一个被验证过很多次的高性价比工具。

最后再分享一个小技巧。我面试别人时，如果候选人在哈希集合法里卡住了，我通常会提示一句：“想一想怎么才能让每个数字只被数一次。”这句话几乎每次都能让候选人豁然开朗。这道题从想出排序方案到真正写出高效解法的过程，其实就是从“直觉解题”到“复杂度导向解题”的一次跨越。我自己最开始也是先写了排序，被复杂度卡住后重新思考才摸到门道。后来刷多了就会发现，很多看似唬人的问题，只要把“什么操作是高频的、什么信息是可以预计算的”想清楚，答案往往会自己浮出来。