LC128　最长连续序列¶

中等通过率 48.7%python3核心代码模式哈希样例通过牛客 AC并查集数组哈希表

牛客原题　源码

讲解章节：哈希表

一句话

装进集合，只从「序列起点」往右扩，总步数被摊还成 O(n)。

解题思路¶

这题考什么¶

要找的是「数值上连续」的最长一段，与元素在原数组里的位置无关。排序再扫一遍是最直观的做法，但排序本身就是 O(n log n)，而题面明确要求 O(n)，所以排序这条路直接被规格排除。

O(n) 的做法建立在两个观察上：

1. 值是否存在，用哈希集合查是 O(1)。于是「x 后面有没有 x+1」
   这种问题不必扫数组。
2. 每条连续序列只应该被走一次。判据是**只从起点起跳**：
   x 是某条序列的起点，当且仅当 x - 1 不在集合里。

有了第 2 条，算法是这样的：把所有数丢进 set（顺带去重），遍历 set 里的每个 x，若 x - 1 存在就跳过（x 是中间元素，它所在的序列会由更左边的起点负责），否则从 x 开始一路问 x+1、x+2、… 在不在，数出这条序列的长度。

为什么这仍是 O(n) 而不是 O(n^2)：内层的 while 只在 x 是起点时才跑，而每条序列只有一个起点，内层总步数等于所有序列的长度之和，也就是集合的大小。外层 O(n) + 内层合计 O(n)，摊还下来仍是线性。去掉 x - 1 not in num_set 这道闸，长序列会被它的每个元素各扫一遍，形如 [1, 2, 3, …, n] 的数据立刻退化成 O(n^2)。哈希集合见哈希表。

数据规模与复杂度¶

0 <= n <= 1e5，-1e9 <= nums[i] <= 1e9。值域跨 2e9，开桶计数或用数组下标标记都不可行（内存直接爆），只能走哈希。时间 O(n)：建集合 O(n)，外层遍历 O(n)，内层扩展合计 O(n)。空间 O(n)：集合最多装 n 个互不相同的值。对照排序做法的 O(n log n)，1e5 时两者实际耗时差别不大，但题面把 O(n) 写进了要求里。

坑在哪¶

起点判据不能省。if x - 1 in num_set: continue 是整题的复杂度所在，不是优化——没有它，[1, 2, …, 1e5] 这种数据的内层循环会跑 1e5 + (1e5 - 1) + … 约等于 5e9 步。
必须先去重再遍历，而且遍历的是 set 而不是原数组。题面示例 3 的 nums = [1, 0, 1, 2] 有重复的 1；若遍历原数组，重复元素会让同一个起点被处理多次（结果仍对，但白跑），更要紧的是重复元素不该让长度多算——集合天然解决了这点， [1, 0, 1, 2] 的答案是 3 而不是 4。
空数组要返回 0。这里靠 ans 的初值 0 兜住：集合为空时循环一次都不进。若把 ans 初始化成 1 之类的值，空输入会返回 1。
内层用 while x + 1 in num_set 逐个问，而不是去删除已访问的元素。删除也能保证不重复走，但会边遍历边改集合，Python 下直接 RuntimeError（迭代期间容器大小变了）。
严格比对：返回的是长度这一个整数，没有多解可言。

样例复核¶

nums = [100, 4, 200, 1, 3, 2]，集合 {1, 2, 3, 4, 100, 200}。

x=1    0 不在集合 -> 是起点，往右数 2、3、4 都在，5 不在，长度 4
x=2    1 在集合   -> 跳过
x=3    2 在集合   -> 跳过
x=4    3 在集合   -> 跳过
x=100  99 不在    -> 是起点，101 不在，长度 1
x=200  199 不在   -> 是起点，201 不在，长度 1

最长 4，与样例一致。内层总步数 4 + 1 + 1 = 6，正好是集合大小。

参考实现¶

solutions/leetcode/LC128/sol.py
from typing import List, Optional


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # 转成集合：一是把「某个值在不在」压成 O(1) 查询，二是顺手去重，
        # 让 [1, 0, 1, 2] 里重复的 1 不会把长度算多
        num_set = set(nums)
        ans = 0                         # 初值 0 同时兜住空数组的情形
        for x in num_set:
            # 循环不变量：只有序列**起点**才允许往下扩。
            # x - 1 存在说明 x 是某条序列的中间元素，那条序列会由它真正的起点走完，
            # 这里跳过。这道闸把内层的总步数摊还成 O(n)，去掉就退化成 O(n^2)
            if x - 1 in num_set:
                continue
            # 从起点一路往右问下一个数在不在，数出这条序列有多长
            cur = x
            length = 1
            while cur + 1 in num_set:
                cur += 1
                length += 1
            # 遍历的是集合本身，所以全程不能增删元素，只能读
            if length > ans:
                ans = length
        return ans

LC128 最长连续序列¶