最长连续序列为什么能用哈希集合做到 O(n)？

简化版

最长连续序列先把所有数放进 HashSet。只从“连续段起点”开始扩展：如果 x - 1 不存在，才从 x 往后数 x+1, x+2...。每个数最多被扩展访问一次，平均 O(n)。

详细版

排序可以 O(n log n) 解决，但哈希集合能把“某个数是否存在”降为平均 O(1)。关键优化是不要从每个数都向后扩展，只从没有前驱的数开始。

int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int x : nums) set.add(x);
    int ans = 0;
    for (int x : set) {
        if (!set.contains(x - 1)) {
            int cur = x;
            int len = 1;
            while (set.contains(cur + 1)) {
                cur++;
                len++;
            }
            ans = Math.max(ans, len);
        }
    }
    return ans;
}

去重由 HashSet 自动完成，重复数字不影响连续段长度。

完整版教学

一、题目为什么不能只排序

最长连续序列要求找值上连续的最长长度，不要求原数组位置连续。例如 [100,4,200,1,3,2] 的答案是 [1,2,3,4]，长度 4。排序后很直观，但复杂度 O(n log n)。

哈希解法的目标是避免排序：只要能快速判断 x+1 是否存在，就能从起点一路扩展出连续段。

二、为什么要用 HashSet

HashSet 保存所有出现过的数字，回答“某个值在不在集合里”。它不关心下标，也不关心次数。连续序列只关心值是否存在，所以 Set 比 Map 更贴合。

nums = [100,4,200,1,3,2]
set = {1,2,3,4,100,200}
从 1 扩展: 1 -> 2 -> 3 -> 4, 长度 4

这类“快速存在性判断”是哈希集合最常见的用法。

三、为什么只从起点扩展

如果从每个数都向后扩展，1,2,3,4 会被重复扫描：从 1 扫 4 个，从 2 扫 3 个，从 3 扫 2 个。优化方法是只从没有前驱的数开始，也就是 x - 1 不在集合中。

x	x-1 是否存在	是否作为起点
1	否	是
2	是	否
3	是	否
100	否	是

这样每段连续序列只会被完整扫描一次。

四、复杂度为什么是 O(n)

外层遍历 Set 中每个不同数字一次。内层 while 看起来可能很多，但它只发生在连续段起点，并且一段中的每个数字只会被某个起点向后访问一次。因此所有 while 总访问次数不超过不同数字数量。

总成本 = 建 set O(n) + 找起点 O(n) + 扩展总次数 O(n)

所以平均时间 O(n)，空间 O(n)。这里的 O(1) 仍然是哈希表平均意义下的。

五、重复数字和边界

重复数字要去掉，否则排序解法还要跳过重复值；HashSet 天然去重。例如 [1,2,2,3] 的连续长度是 3，不是 4。

边界上，如果数组为空，答案是 0。如果数字接近整数上限，cur + 1 可能溢出，严格工程代码需要注意；算法题一般不刻意卡这个点，但面试追问可以提到。

六、常见误区与追问

记忆钩子：最长连续序列只从“没有前驱的人”出发。不是起点的人，迟早会被自己的起点覆盖。

误区：从每个数都向后扩展仍是 O(n)。 连续长段会被重复扫描，可能退化到 O(n²)。
误区：需要 Map 记录下标。 题目只关心值连续，不关心原位置，Set 就够。
误区：重复数字能增加长度。 连续序列按不同值计数，重复值不增加长度。
追问：排序解法能不能用？ 可以，O(n log n)，空间可更低；哈希解法更快但多用 O(n) 空间。
追问：为什么判断 x-1 而不是 x+1？ x-1 不存在说明 x 是起点，只有起点需要扩展。
追问：最坏情况一定 O(n) 吗？ 理论上哈希严重冲突会退化，工程实现依赖哈希质量和冲突处理。

七、加强记忆

最长连续序列的关键不是“连续扩展”，而是“只从起点扩展”。HashSet 负责 O(1) 判断存在性，x-1 不存在负责识别起点，x+1 while 负责计算长度。把这三步串起来，就能解释 O(n) 的来源。

简化版

详细版