题型地图 56天全屏 141题

当前：LC128 · 最长连续序列 · 首次出现于 Day 3 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

57 / 141回到 Day 3 卡片 141 题索引

LC128

最长连续序列 · 为什么只能从起点扩展才是 O(n)

HashSet · 起点判断

题目要求 O(n),所以不能排序。先用 HashSet 去重并支持 O(1) 查询,只对"前驱不存在"的数启动扩展,把每段序列只数一次。

当前输入

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

起点只有一个:数 1。从 1 开始 → 2 → 3 → 4。

最长连续序列长度

序列 = [1, 2, 3, 4]

错误直觉 · 每个数都扩展时间 O(n²) · 空间 O(n)

同一段被多个 pivot 重复扫描

正解 · 遍历 set + 起点判断时间 O(n) · 空间 O(n)

每段只被它的最小值启动一次

三个测试用例 · 切换后整段动画会重算

三段教学结构

① 错误直觉

每个数都向左右扩展 → 同段被反复计数

② 起点判断

只有 num-1 不在 set,num 才是起点

③ 正确扩展

从起点 num 出发查 num+1, num+2…

题目输入:nums = [100, 4, 200, 1, 3, 2]Step 1/33

当前发生了什么

输入:nums = [100, 4, 200, 1, 3, 2]

起点只有一个:数 1。从 1 开始 → 2 → 3 → 4。

机器状态

nums 长度: 6
set 大小: 6
当前 num: —
起点测试 num-1: —
currentLen: 0
maxLen: 0

为什么这一步是对的

先把题目 O(n) 的约束记牢 —— 这会直接排除排序解法。

面试该怎么说 · 开题第一句话:"题目要求 O(n),所以不能排序。" 然后引出 HashSet。

原数组 nums (会有重复元素)

100[0]

4[1]

200[2]

1[3]

3[4]

2[5]

set 视图 · 遍历 set,不是遍历 nums

起点只有一个:数 1。从 1 开始 → 2 → 3 → 4。

set = {

100

200

}

maxLen 当前值

目前最长段

—

当前 num起点非起点(continue)本段命中probe 命中probe 落空

代码同步 · Go

题目

1func longestConsecutive(nums []int) int {
2    if len(nums) == 0 {
3        return 0
4    }
5    numSet := make(map[int]struct{}, len(nums))
6    for _, n := range nums {
7        numSet[n] = struct{}{}
8    }
9    maxLen := 0
10    for num := range numSet {                // 遍历 set,不是 nums
11        if _, ok := numSet[num-1]; ok {
12            continue                         // 非起点直接跳过
13        }
14        cur, length := num, 1                // num 是起点
15        for {
16            if _, ok := numSet[cur+1]; !ok {
17                break
18            }
19            cur++
20            length++
21        }
22        if length > maxLen {
23            maxLen = length
24        }
25    }
26    return maxLen
27}

注意第 10 行:Go 写的是 for num := range numSet — 遍历 set 的 key,而不是 for _, num := range nums。后者会让重复元素触发多次"起点扩展",复杂度无法证为 O(n)。

本步不变量

还没建任何结构,只是把题目摆好。

剧本时间线 · 共 33 步

三条不变量 · 把 O(n) 证明撑起来

①任何连续序列只会从它的最小值开始扩展一次。
②非起点 x 一定有 x-1 存在,所以它属于某个更早开始的连续段,不需要再次扩展。
③遍历 set 后,每个唯一数字最多作为内层 while 的一部分被访问一次,因此总复杂度 O(n)。

面试 · 一段话讲清楚

这题要求 O(n),所以不能排序。我先用 HashSet 去重并支持 O(1) 查询。然后遍历 set 中的每个唯一数字,只有当 num-1 不存在时, num 才是一个连续段的起点,再向右查 num+1, num+2。这样每段只会被它的最小值启动一次,避免重复扩展,整体 O(n)。

常见误区

✗ 遍历 nums 而不是 set —— 重复元素会让同一个数被多次当作起点候选,O(n) 证明立刻崩盘。Go 中写 for num := range numSet。
✗ 对每个数都向左右扩展 —— 同一段会被段中所有 L 个数各扫一次,退化为 O(n²)。
✗ 忘记空数组守卫 —— len(nums)==0 直接返回 0,避免后续 maxLen 行为意外。
✗ 把空间复杂度说成 O(1) —— set 占 O(n)。