128. 最长连续序列

解题思路：哈希集合 + 智能起点判断

要实现 O(n) 时间复杂度，不能排序（排序是 O(n log n)），也不能对每个数都向前后暴力扩展（会重复计算）。

核心思想：

将所有数字放入 HashSet，实现 O(1) 查找。
只从“连续序列的起点”开始扩展，避免重复工作。
- 什么是起点？若 x 是起点，则 x - 1 不在集合中。
对每个起点 x，依次检查 x+1, x+2, ... 是否在集合中，统计长度。

这样，每个数字最多被访问两次（一次作为非起点被跳过，一次作为序列中的元素被扩展），总时间复杂度为 O(n)。

Java 实现

import java.util.*;

public class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        
        int maxLength = 0;
        
        // 注意，遍历 numSet 保证 n 次
        for (int num : numSet) {
            // 只有当 num 是连续序列的起点时才开始计数
            if (!numSet.contains(num - 1)) {
                int currentNum = num;
                int currentLength = 1;
                
                // 向后扩展
                while (numSet.contains(currentNum + 1)) {
                    currentNum++;
                    currentLength++;
                }
                
                maxLength = Math.max(maxLength, currentLength);
            }
        }
        
        return maxLength;
    }
}

算法正确性说明

为什么不会漏掉最长序列？
因为任何连续序列都有唯一的最小值（起点），我们一定会在遍历到该起点时完整地探索整个序列。
为什么时间复杂度是 O(n)？
- 外层循环最多执行 n 次（集合大小 ≤ n）
- 内层 while 循环在整个算法运行过程中总共最多执行 n 次（每个数字最多被访问一次用于扩展）
- 所以总操作次数 ≤ 2n → O(n)
空间复杂度：O(n)，用于存储哈希集合。

边界情况处理

空数组 → 返回 0
重复元素 → 哈希集合自动去重，不影响结果
单个元素 → 返回 1