128. 最长连续序列（Longest Consecutive Sequence）

频次 ★★★★ · 难度 🟡 · 高频：字节/阿里

题目

给定未排序整数数组，找出数字连续（值连续，位置无关）的最长序列长度。要求 O(n) 时间。

示例：

输入: [100,4,200,1,3,2]
输出: 4    （连续序列 1,2,3,4）

思路

排序做是 O(n log n)，题目逼你用哈希：全部数字入 HashSet，然后只从”序列起点”向右数——一个数 x 是起点当且仅当 x-1 不在集合里。从起点开始 x+1, x+2, ... 逐个查集合延伸，记录最长长度。

关键在”只从起点展开”：每个数最多被访问两次（一次判起点、一次被某条序列扫过），总时间 O(n)。

代码

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int n : nums) set.add(n);
    int best = 0;
    for (int x : set) {
        if (set.contains(x - 1)) continue;   // 不是起点,跳过(去重的关键)
        int len = 1;
        while (set.contains(x + len)) len++; // 从起点向右延伸
        best = Math.max(best, len);
    }
    return best;
}

复杂度

• 时间：O(n) —— 每个元素判起点 O(1)；只有真起点才展开，所有展开步数之和等于各序列总长 ≤ n
• 空间：O(n) —— HashSet

边界条件

• 空数组：返回 0
• 全部重复（[1,1,1]）：set 去重后长度 1
• 单调递减输入：不影响，集合无序，按起点逻辑照常工作

变式

• 要求返回序列本身：起点展开时顺带记录区间 [x, x+len-1]
• 数据流版/支持动态插入：用并查集把 x 与 x+1 合并，size 数组维护连通块大小

易错点

• 不判起点直接对每个数向右展开 → 最坏 O(n²)（[1,2,3,...,n] 每个点都扫到尾），这是本题最常见的”看似 O(n) 实则超时”
• 遍历时应遍历 set 而不是原数组，否则大量重复元素会重复做起点判断（不影响正确性但浪费）
• while (set.contains(x + len)) 中用 len 做偏移，避免修改 x 后影响外层判断

面试追问

• 为什么复杂度是 O(n) 而不是 O(n²)？ 回答要点：展开只发生在起点，且每条序列只被它唯一的起点展开一次，展开总步数 = 所有序列长度之和 ≤ n
• 如果内存放不下所有数呢？ 外部排序后线性扫描（退回 O(n log n)），或按值域分片多轮处理——哈希方案的前提是数据能进内存

关联题

• 同套路：1. 两数之和 —— 同为”哈希以空间换时间”，把查找从 O(n) 压到 O(1)
• 进阶：并查集解法（x 与 x+1 合并），并查集专题见并查集
• 易混：560. 和为 K 的子数组 —— 同用哈希但存的是前缀和，本题存的是元素本身
• 知识点：HashSet 底层就是 HashMap 的 key 集，见集合框架