当前位置：首页 > news >正文

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

news 2026/7/1 2:39:31

📝 前言

今天在刷 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. 核心逻辑：去重与定位“起点”

我们可以分两步走：

去重与存储：先把所有数字放入HashSet中，这样我们不仅去除了重复元素，还能在 O(1) 的时间内判断一个数是否存在。
寻找序列起点：
- 如果我们对集合中的每一个数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来存储数组中的元素，以空间换时间。