【LeetCode Hot100】128. 最长连续序列 - Java O(n) 解法详解

📝 前言

今天在刷 LeetCode 热题 100 时，碰到了第 128 题 “最长连续序列”。这是一道非常经典的题目，考察的重点是如何在不排序的情况下，利用哈希表在 O(n) 的时间复杂度内完成查找。

乍一看这道题如果用 Arrays.sort() 排序后遍历，时间复杂度是 O(nlog n)，但这道题明确要求 O(n)，所以必须换一种思路。记录一下我的解题心得和最终代码。

📚 题目描述

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

示例 1：

输入： nums = [100,4,200,1,3,2] 输出： 4 解释： 最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

提示：

• 请设计并实现时间复杂度为 O(n) 的算法。

💡 解题思路

1. 为什么不能排序？

题目硬性要求时间复杂度为 O(n)。我们知道标准的排序算法（如快排、归并）最快也是 O(nlog n)，所以排序这条路走不通。我们需要一种能够快速查找的数据结构，哈希表 (HashSet) 是最佳选择。

2. 核心逻辑：去重与定位“起点”

我们可以分两步走：

1. 去重与存储：先把所有数字放入 HashSet 中，这样我们不仅去除了重复元素，还能在 O(1) 的时间内判断一个数是否存在。
2. 寻找序列起点：
   • 如果我们对集合中的每一个数 x 都去尝试向后枚举 (x+1, x+2...)，时间复杂度最坏会达到 O(n^2)。
   • 关键优化点：我们只从序列的起点开始查找。
   • 如何判断起点？ 如果一个数 x，它的前驱 x-1 不在集合中，那么 x 一定是某个连续序列的第一个数。
   • 只有当 x 是起点时，我们才开始向后匹配 x+1, x+2 等等，统计长度。

3. 一个小优化

在统计过程中，如果当前找到的最长序列长度已经超过了哈希表中剩余元素的一半（或者总数的一半），其实就可以提前结束循环了，因为剩下的元素数量不可能凑出更长的序列。

💻 代码实现 (Java)

代码相比官方题解做了变量名的语义化修改，使其更符合工程规范，方便阅读。

class Solution {
    public int longestConsecutive(int[] nums) {
        // 1. 预处理：将数组元素放入 HashSet，实现去重和 O(1) 查询
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int maxLen = 0;
        int totalNums = numSet.size();

        // 2. 遍历集合中的每个元素
        for (int num : numSet) {
            // 核心剪枝逻辑：
            // 只有当 num-1 不存在时，num 才是一个连续序列的【起点】
            // 如果 num-1 存在，说明 num 已经被计算过了，直接跳过
            if (!numSet.contains(num - 1)) {
                
                int currentNum = num;
                int currentLen = 1;

                // 从起点开始，不断向后寻找连续的数字
                while (numSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentLen += 1;
                }

                // 更新最大长度
                maxLen = Math.max(maxLen, currentLen);

                // 【可选优化】：如果当前找到的长度已经超过总数的一半，
                // 那么剩下的元素不可能组成更长的序列，直接退出
                if (maxLen > totalNums / 2) {
                    break;
                }
            }
        }

        return maxLen;
    }
}

🔍 复杂度分析

• 时间复杂度：O(n)
  • 虽然代码里有一个 while 循环嵌套在 for 循环里，但仔细分析会发现：由于 if (!numSet.contains(num - 1)) 的限制，数组中的每个数最多只会被访问两次（一次是作为序列起点被访问，一次是作为序列的一部分被内部 while 访问）。
  • 因此总的操作次数是线性的。
• 空间复杂度：O(n)
  • 我们需要一个 HashSet 来存储数组中的元素，以空间换时间。

🎯 总结

这道题是哈希表运用的典范。解决很多 O(n) 复杂度问题的秘诀往往就在于“如何避免重复计算”。在这道题里，通过判断 x-1 是否存在，精准地锁定了每个序列的头部，从而避免了大量的无效枚举。