128 最长连续序列

一、题目

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

二、题解

思路： 先把所有数字放入 HashSet，借助 O(1)O(1) 查找并自动去重。然后遍历集合，只从每个连续序列的「起点」开始向后枚举：当 num - 1 不在集合中时，num 才是起点，由它不断检查 num + 1、num + 2 …… 是否存在，统计当前序列长度并更新最大值。这一「只从起点出发」的判断保证每个数至多被向后访问一次，从而把整体复杂度降到 O(n)O(n)。

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int longestConsecutive(int[] nums) {
        // 边界处理：空数组或 null，最长连续序列为 0
        if (nums == null || nums.length == 0) return 0;

        // 将所有数字存入 HashSet，实现 O(1) 的查找效率
        // 同时自动去重，避免重复数字干扰
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        // 记录全局最长连续序列的长度
        int longestStreak = 0;

        // 遍历 Set 中的每个数字
        for (int num : set) {

            // 【核心优化】只有当 num 是一个连续序列的"起点"时，才开始向后枚举
            // 起点的判断标准：num - 1 不在集合中
            // 这样可以确保每个连续序列只会被完整遍历一次，不会重复计算
            // 例如序列 [1,2,3,4]，只有 1 满足 !set.contains(0)，所以从 1 开始
            if (!set.contains(num - 1)) {

                // currentNum 从当前起点开始，向后逐个检查
                int currentNum = num;

                // currentStreak 记录当前连续序列的长度，起点至少为 1
                int currentStreak = 1;

                // 不断检查 currentNum 的下一个数字是否在集合中
                // 如果在，说明连续序列还在延续
                while (set.contains(currentNum + 1)) {
                    currentNum += 1;      // 指针后移到下一个数字
                    currentStreak += 1;   // 当前连续长度 +1
                }

                // 更新全局最长长度
                longestStreak = Math.max(longestStreak, currentStreak);
            }
        }

        return longestStreak;
    }
}

时间复杂度：O(n)O(n)

空间复杂度：O(n)O(n)

评论