 解法详解)
📝 前言
今天在刷 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来存储数组中的元素，以空间换时间。
🎯 总结
这道题是哈希表运用的典范。解决很多 O(n) 复杂度问题的秘诀往往就在于“如何避免重复计算”。在这道题里，通过判断x-1是否存在，精准地锁定了每个序列的头部，从而避免了大量的无效枚举。