最长连续序列：只从链条的开头数起
O(n) 的关键不是记忆，而是「只在起点开始数」，让每个数最多被数一次。
把所有数放进哈希集合。遍历每个数 x，只有当 x−1 不在集合里（x 是一条连续链的起点）时，才从 x 开始向后数 x, x+1, x+2…，统计链条长度。每个数至多被数一次，整体 O(n)。
给你一个未排序的整数数组，找出数字连续的最长序列的长度，要求 O(n) 时间。
所谓连续序列，指形如 [1,2,3,4] 这样的等差数列，公差为 1。
排序解法 O(n log n) 显然能做，但题目明确要求 O(n)。关键洞察藏在「起点判定」里。
先明确问题
示例：nums = [100,4,200,1,3,2]，最长连续序列是 [1,2,3,4]，长度 4。
示例：nums = [0,3,7,2,5,8,4,6,0,1]，答案是 9（0 到 8 全有）。
数字可能重复，重复元素不贡献长度。
基准解：排序后扫一遍
排序后相等的数相邻，连续的数也相邻。扫一遍统计连续段长度。
O(n log n) 时间。正确，但题目要 O(n)，必须另想办法。
排序的冗余在于：我们只需要「某个数是否存在」，排序却把整个相对顺序都排出来了。
集合 + 起点判定
把所有数放进哈希集合 seen，回答「x 在不在数组里」只需 O(1)。
遍历每个数 x，只处理一种情况：x−1 不在集合里。此时 x 是一条连续链的起点。
为什么要判定起点？如果 x−1 存在，那么 x 已经被前一个起点的链条覆盖了，从 x 再数一遍就是重复劳动——正是排序法的缺点。
只有起点才启动链条，每个数最多被「数」一次，于是总时间 O(n)。
起点「只在链头启动」把每个元素的访问次数从 O(n) 压到 O(1)——O(n²) 变 O(n) 往往就差这一下。
从起点向后延伸
确定起点 x 后，用一个 while 循环：x+1 在集合里就继续，x+2、x+3……直到断掉。统计链条长度。
对 [100,4,200,1,3,2]：起点 1 → 1,2,3,4 长度 4；起点 4 不处理（4−1=3 在集合里）；起点 100 → 100 长度 1；起点 200 → 200 长度 1。答案是 4。
注意 4 不作为起点启动，因为它的链条 1→2→3→4 已经由起点 1 数过了。
为什么总时间是 O(n)
每个数只做两件事：作为非起点时被看一眼就跳过（O(1)）；作为起点时被自己的链条数到（它只属于一条链）。
链条不会重叠：从不同起点延伸出来的序列互不相交。所以所有链条的长度总和 ≤ n。
起点判定的 O(1) 检查用集合完成，整体严格 O(n)。
十行 Go：集合 + 起点延伸
func longestConsecutive(nums []int) int {seen := make(map[int]bool, len(nums))for _, x := range nums { seen[x] = true }best := 0for x := range seen {if seen[x-1] { continue }length := 1for y := x + 1; seen[y]; y++ { length++ }if length > best { best = length }}return best}
1哈希集合记录所有数。
2填充集合。
3遍历每个数 x。
4x−1 存在则跳过——x 不是起点。
5从 x 向后延伸，统计长度。
6更新最大值。
总结
集合判存在，起点才开始数——每个数至多数一次，O(n) 到手。
- 排序 O(n log n) 可行，但题目要求 O(n)。
- 起点判定（x−1 不在集合）避免了从链条中间重复计数。
- 链条互不相交，总长度 ≤ n，严格 O(n)。