Leetcode Hot 100 最长连续序列

Leetcode Hot 100 第三篇，来到这道很适合拿来练“哈希集合 + 起点判断”的经典题：最长连续序列。

这题看起来像排序题，很多人第一反应都是先排个序再说。但题目偏偏就想看你别走老路，直接点名要求：

请你设计并实现时间复杂度为 O(n) 的算法。

这时候就不能老想着排队站好再数人头了。得换个思路：用哈希集合查存在性，只从连续段的起点出发往后扩展。

题目链接#

LeetCode 128. 最长连续序列

题目描述#

给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

最长连续序列题目截图

题目里的“连续”是什么意思？#

这里说的连续，不是指在原数组里挨着放。而是指数值上连续。

比如：

1
[100, 4, 200, 1, 3, 2]

虽然 1、2、3、4 在原数组里站得乱七八糟，但它们数值上是连续的，所以最长连续序列长度就是：

1
4

解题思路：哈希集合 + 只从起点开始扩展#

这题的核心，不是把所有数排个序，而是先把所有数丢进哈希集合里。

这样做的好处是：

查某个数在不在集合里，平均复杂度是 O(1)
我们可以非常快地判断一个数是不是连续段的开头

关键观察是：

如果 x - 1 也在集合里，那 x 就不是一段连续序列的起点。

既然不是起点，那就没必要从它开始数。因为这段序列，迟早会从更前面的那个数开始被统计到。

所以整套逻辑可以概括成：

先把数组去重后放进集合
遍历集合中的每个数 x
如果 x - 1 存在，跳过
如果 x - 1 不存在，说明 x 是起点
从 x 开始不断检查 x + 1、x + 2、x + 3 … 是否存在
统计这一段的长度，更新答案

这题真正省时间的地方，就在这句：

不是每个数都往后扫，只让“起点”负责开跑。

代码实现#

1
class Solution(object):
2
    def longestConsecutive(self, nums):
3
        """
4
        :type nums: List[int]
5
        :rtype: int
6
        """
7
        hash_set = set(nums)
8
        ans = 0
9

10
        for x in hash_set:
11
            # 只有当 x 是连续序列起点时，才开始向后扩展
12
            if x - 1 in hash_set:
13
                continue
14

15
            y = x
16
            while y in hash_set:
17
                y += 1
18

19
            ans = max(ans, y - x)
20

21
        return ans

代码解析#

我们一段一段拆开看。

1. 先把数组放进哈希集合#

1
hash_set = set(nums)

这一步有两个作用：

作用一：去重#

如果数组里有重复元素，比如：

1
[1, 2, 2, 3]

放进集合后就会变成：

1
{1, 2, 3}

重复数字不会影响最长连续序列的长度，去掉更省事。

作用二：支持 `O(1)` 级别查找#

后面我们要频繁判断：

x - 1 在不在？
x + 1 在不在？
x + 2 在不在？

如果不用集合，而是每次在数组里查，效率会很难看。

2. 遍历集合里的每个数#

1
for x in hash_set:

我们不直接遍历原数组，而是遍历集合。

这样做更干净，因为：

不会重复处理相同数字
逻辑上更贴近“检查某个值是否存在”这件事

3. 判断当前数字是不是起点#

1
if x - 1 in hash_set:
2
    continue

这是整题最关键的一刀。

它的意思是：

如果 x - 1 存在
那说明 x 前面还有数
所以 x 不是这段连续序列的起点
那就别从它开始重复统计了，直接跳过

比如集合里有：

1
{1, 2, 3, 4}

当遍历到：

1 时，0 不在集合里，所以 1 是起点，可以开始数
2 时，1 在集合里，所以 2 不是起点，跳过
3 时，2 在集合里，继续跳过
4 时，3 在集合里，也跳过

这样一来，整段连续序列只会被统计一次。

4. 从起点开始一路往后找#

1
y = x
2
while y in hash_set:
3
    y += 1

如果 x 是起点，我们就从它开始不断检查下一个数还在不在集合里。

比如从 1 开始：

1 在
2 在
3 在
4 在
5 不在

那循环结束时：

1
y = 5

说明从 1 到 4 是一整段连续序列。

5. 计算这一段长度#

1
ans = max(ans, y - x)

这里很多人会愣一下，为什么不是 y - x + 1？

因为循环退出时，y 已经是第一个不存在的数了。

举个例子：

起点 x = 1
连续段是 1, 2, 3, 4
循环停下时 y = 5

所以长度就是：

1
5 - 1 = 4

刚好正确。

示例推演#

假设输入：

1
nums = [100, 4, 200, 1, 3, 2]

先转成集合：

1
{100, 4, 200, 1, 3, 2}

下面开始遍历。

遍历到 `100`#

99 不在集合里
所以 100 是起点
往后看：101 不在
这一段长度是 1

当前答案：

1
ans = 1

遍历到 `4`#

3 在集合里
所以 4 不是起点
跳过

遍历到 `200`#

199 不在集合里
所以 200 是起点
往后看：201 不在
这一段长度也是 1

答案还是：

1
ans = 1

遍历到 `1`#

0 不在集合里
所以 1 是起点
往后看：2 在、3 在、4 在、5 不在
所以这一段长度是：

1
5 - 1 = 4

更新答案：

1
ans = 4

最后返回 4。

为什么这样能做到 O(n)#

很多人第一次看会问：

外层一个 for，里面一个 while，这不看着像 O(n^2) 吗？

表面上像，实际上不是。

因为每个数虽然都可能被外层 for 遍历一次，但真正进入 while 连续扩展的，只有那些“起点”。

更关键的是：

每个元素最多只会被某一段连续序列向后扫描一次
不会出现每个数都从自己开始把后面所有数重扫一遍的情况

所以总体上，所有 while 加起来依然是线性的。

因此总时间复杂度是：

1
O(n)

复杂度分析#

时间复杂度#

构建集合：O(n)
遍历集合：O(n)
所有连续扩展过程合起来：O(n)

所以总时间复杂度为：

1
O(n)

空间复杂度#

集合中最多存放 n 个不同元素，所以空间复杂度为：

1
O(n)

关于一个常见“优化”误区#

有些写法会在统计过程中加类似这样的剪枝：

1
if ans * 2 >= len(hash_set):
2
    break

看起来像是在说：

“如果当前最长长度已经超过集合元素数量的一半，那差不多可以认定最优了。”

但这其实不严谨。

因为：

len(hash_set) 只是去重后的元素总数
当前遍历顺序是无序的
后面仍然可能存在更长的连续序列

也就是说，这种剪枝没有可靠的数学保证。

刷题或者面试时，建议直接写标准版本，短、稳、清楚，不给自己埋雷。

这种写法的关键点#

1. 不是找到一个数就往后冲#

只有当 x - 1 不存在时，才说明 x 是起点。

这一步是避免重复统计的核心。

2. 用集合不是为了排序，而是为了快查#

集合不负责顺序，负责的是：

“这个数在不在？”

而这正是这道题最需要的能力。

3. 这题不是双指针，也不是排序贪心#

如果先排序，也能做出来，但时间复杂度通常会变成：

1
O(n log n)

题目既然明确要求 O(n)，那哈希集合就是更对味的正解。

小结#

这题表面在问“最长连续序列”，本质上在考的是：

你能不能利用哈希集合的快速查找，避免重复扫描。

真正的关键句只有一句：

只从连续序列的起点开始往后找。

一旦抓住这个点，这题就会从“好像有点乱”，瞬间变成“哦，原来就是这么回事”。

如果只记一句话，那就是：

不是每个数都配开局，只有起点才有资格发车。

Hot 100 第三篇，继续往前拱。算法路上别急着卷天卷地，先把每一步走稳，虾就能越爬越远。🦐