 复杂度？)
在 LeetCode 的算法题中，“最长连续序列” (Longest Consecutive Sequence)是一道非常经典的Hot 100题目。它考察的不是复杂的算法模板，而是对哈希表特性的灵活运用以及对时间复杂度的精确控制。
1. 题目核心难点
题目描述：给定一个未排序的整数数组nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
关键限制：请你设计并实现时间复杂度为的算法解决此问题。
为什么不能排序？
看到“连续序列”，直觉反应通常是先排序，然后遍历一遍统计。
排序算法（如快速排序、归并排序）的时间复杂度下限是
。
题目严格要求
，这意味着排序是被禁止的。我们必须在不排序的情况下，通过“查找”来还原序列。
2. 核心思路：哈希表 + “跳过逻辑”
要在时间内知道“某个数字是否存在”，只能依靠哈希表 (HashSet)。
步骤一：去重与快速查找
首先，将数组中所有元素放入HashSet中。
目的 1：实现
的查找复杂度。
目的 2：去重（虽然这一步不是必须的，但遍历 Set 比遍历原数组更稳健，详见后文分析）。
步骤二：寻找序列的“起点” (关键优化)
这是算法能达到的核心原因。
假设数组是 [100, 4, 200, 1, 3, 2]。哈希表中包含了这些数字。
当我们遍历到数字 3 时，我们要不要开始数数（寻找 4, 5...）？
不要。因为
3的前面有2。既然2存在，3肯定不是一个连续序列的开头。我们应该等待遍历到2（甚至1）时再处理。规则：只有当
num - 1不在哈希表中时，num才是序列的起点，我们才开始向后计数。
3. 代码实现与详解
Java
class Solution { public int longestConsecutive(int[] nums) { // 1. 使用 HashSet 存储所有数字，实现 O(1) 查询并去重 Set<Integer> num_set = new HashSet<Integer>(); for (int num : nums) { num_set.add(num); } int longestStreak = 0; // 2. 遍历哈希表中的每个数字 for (int num : num_set) { // 3. 【关键判断】只有当 num 是序列的起点时（即 num-1 不存在），才开始匹配 if (!num_set.contains(num - 1)) { int currentNum = num; int currentStreak = 1; // 4. 不断查询 num+1, num+2... 是否存在 while (num_set.contains(currentNum + 1)) { currentNum += 1; currentStreak += 1; } // 5. 更新最大长度 longestStreak = Math.max(longestStreak, currentStreak); } } return longestStreak; } }4. 深度解析：为什么这是 O(N)？
很多初学者看到for循环里套了一个while循环，第一反应就是：“这不是吗？”
其实不然。我们要从每个元素被访问的次数来分析：
外层循环：每个元素最多被访问 1 次。
内层
while循环：只有当一个数是“起点”时，才会进入
while。举例
[1, 2, 3, 4]。访问
4：4-1存在，跳过。访问
3：3-1存在，跳过。访问
2：2-1存在，跳过。访问
1：1-1不存在，是起点。进入while，依次访问2, 3, 4。
结论：数组中的每个数字，只会被
while循环内部访问最多一次（就是在统计属于它的那个序列长度时）。
总操作次数(存入Set) +
(外层遍历) +
(内层while累计总次数)。
即，忽略常数后为
。
5. 易错点分析：遍历nums还是遍历Set？
在实现时，有人会习惯写成for (int num : nums)来遍历原数组。虽然在大多数情况下也能通过，但存在隐患。
潜在风险：重复元素的陷阱
如果输入数组包含大量重复的“起点”，例如：
nums = [1, 1, 1, ..., 1, 2, 3, 4, ... 1000]
遍历
nums：程序会遇到第一个1，发现0不在，扫描一遍1到1000。接着遇到第二个1，又扫描一遍1到1000……这将导致算法退化为并超时。
遍历
Set（官方解法）：Set天然去重。无论原数组有多少个1，Set中只有一个1，内层循环只会执行一次。
因此，始终推荐遍历Set而不是原数组，这是保证算法稳定的最佳实践。
总结
解决 LeetCode 128 题的关键在于转换思维：
空间换时间：用哈希表代替排序，消除
的瓶颈。
剪枝优化：通过
!set.contains(x-1)这一判断，精准定位序列起点，避免了对同一个序列中间元素的重复无效计算，将复杂度严格控制在。
