128. 最长连续序列#

public int longestConsecutive(int[] nums) {
    // 边界条件：空数组没有任何连续序列，直接返回 0
    if (nums.length == 0) return 0;

    // 先将数组升序排序，便于线性扫描连续区间
    Arrays.sort(nums);

    // maxLength：记录历史上遇到的最长连续序列长度
    int maxLength = 1;
    // currentLength：记录当前连续序列的长度（以 nums[i] 结尾）
    int currentLength = 1;

    // 从第二个元素开始，与前一个元素比较判断是否连续
    for (int i = 1; i < nums.length; i++) {
        // 若当前值与前一个值相同，属于重复元素，跳过避免干扰长度计算
        if (nums[i] == nums[i-1]) continue;

        // 若当前值恰好等于前一个值 + 1，说明连续序列可以延长
        if (nums[i] == nums[i-1] + 1) {
            // 当前连续长度加 1
            currentLength++;
            // 同步更新全局最大长度
            maxLength = Math.max(maxLength, currentLength);
        } else {
            // 不连续：以当前元素作为新序列起点，长度重置为 1
            currentLength = 1;
        }
    }

    // 返回扫描结束后得到的最长连续序列长度
    return maxLength;
}

首先创建哈希集合：{1, 2, 3, 4, 100, 200}

检查100：
- 99不在集合中，100是起点
- 找101，不存在
- 长度为1

检查4：
- 3在集合中，跳过

检查200：
- 199不在集合中，200是起点
- 找201，不存在
- 长度为1

检查1：
- 0不在集合中，1是起点
- 找2，存在
- 找3，存在
- 找4，存在
- 找5，不存在
- 长度为4

...剩余数字都不是起点，跳过

public int longestConsecutive(int[] nums) {
    // set：哈希集合，用于 O(1) 平均时间判断某个数字是否存在
    Set<Integer> set = new HashSet<>();
    // 预处理：把数组中的所有数字加入集合（重复值会被自动去重）
    for (int num : nums) {
        set.add(num);
    }

    // maxLength：记录遍历过程中发现的最长连续序列长度
    int maxLength = 0;

    // 遍历原数组中的每个数字，尝试把它当作某个连续序列的起点
    for (int num : nums) {
        // 关键剪枝：只有当 num-1 不存在时，num 才可能是一个序列起点
        // 如果 num-1 存在，则 num 一定在某个序列中间，跳过可避免重复计数
        if (!set.contains(num - 1)) {
            // currentNum：从当前起点开始向后探测的数字
            int currentNum = num;
            // currentLength：以 num 为起点的连续序列当前长度，起步为 1（仅包含 num）
            int currentLength = 1;

            // 只要 currentNum+1 还在集合中，说明连续序列还可以继续延长
            while (set.contains(currentNum + 1)) {
                // 向后推进到下一个连续数字
                currentNum++;
                // 序列长度同步加 1
                currentLength++;
            }

            // 一段连续序列统计完成后，更新全局最大值
            maxLength = Math.max(maxLength, currentLength);
        }
    }

    // 返回最终的最长连续序列长度
    return maxLength;
}