LeetCode经典题解：128、最长连续序列

“最长连续序列”是一道极具代表性的数组处理问题， 本文将带你从直观思路出发，逐步推导出最优解法，并通过场景化记忆技巧掌握核心逻辑。

一、题目描述

题目：给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
要求：时间复杂度为 O(n)。

示例：
输入：nums = [100, 4, 200, 1, 3, 2]
输出：4
解释：最长连续序列是 [1, 2, 3, 4]，长度为 4。

二、解法分析：从暴力到最优

方法一：暴力法（直观但超时）

思路

对每个数 x，检查 x+1, x+2, ... 是否存在于数组中，记录最长连续序列的长度。

代码

public int longestConsecutive(int[] nums) {int longestStreak = 0;for (int num : nums) {int currentNum = num;int currentStreak = 1;while (arrayContains(nums, currentNum + 1)) {currentNum += 1;currentStreak += 1;}longestStreak = Math.max(longestStreak, currentStreak);}return longestStreak;
}private boolean arrayContains(int[] arr, int num) {for (int i = 0; i < arr.length; i++) {if (arr[i] == num) {return true;}}return false;
}

复杂度

• 时间复杂度：O(n³)
  • 遍历数组 O(n)
  • 对每个数检查后续 O(n)
  • 每次检查是否存在 O(n)
• 空间复杂度：O(1)

方法二：排序法（O(n log n)，不符合要求但易理解）

思路

先排序数组，再遍历统计连续序列长度。

代码

public int longestConsecutive(int[] nums) {if (nums.length == 0) return 0;Arrays.sort(nums);int longestStreak = 1;int currentStreak = 1;for (int i = 1; i < nums.length; i++) {if (nums[i] != nums[i-1]) {if (nums[i] == nums[i-1] + 1) {currentStreak++;} else {longestStreak = Math.max(longestStreak, currentStreak);currentStreak = 1;}}}return Math.max(longestStreak, currentStreak);
}

复杂度

• 时间复杂度：O(n log n)（排序主导）
• 空间复杂度：O(1)（忽略排序的栈空间）

方法三：哈希表优化（O(n)，最优解）

思路

1. 用哈希表存储所有数：快速判断某个数是否存在（O(1)）。
2. 仅从序列起点开始计数：若 x-1 不存在，则 x 是序列起点，开始向后计数。

代码

public int longestConsecutive(int[] nums) {// 用 HashSet 存储所有数，支持 O(1) 查询Set<Integer> numSet = new HashSet<>();for (int num : nums) {numSet.add(num);}int longestStreak = 0;// 遍历每个数，若它是序列起点，则向后计数for (int num : numSet) {// 若 num-1 不存在，则 num 是序列起点if (!numSet.contains(num - 1)) {int currentNum = num;int currentStreak = 1;// 持续检查 currentNum+1 是否存在while (numSet.contains(currentNum + 1)) {currentNum += 1;currentStreak += 1;}longestStreak = Math.max(longestStreak, currentStreak);}}return longestStreak;
}

复杂度

• 时间复杂度：O(n)
  • 每个数最多被访问两次（一次插入哈希表，一次计数）
• 空间复杂度：O(n)（哈希表存储所有数）

三、最优解法的核心逻辑

1. 为什么用哈希表？

哈希表（HashSet）提供 O(1) 的查找效率，能快速判断某个数是否存在，避免了暴力法中的嵌套循环。

2. 如何避免重复计数？

关键在于只从序列的起点开始计数。例如，对于序列 [1, 2, 3, 4]，我们只在遇到 1 时才开始向后计数，遇到 2, 3, 4 时直接跳过。
判断条件：若 num-1 不存在于哈希表中，则 num 是序列起点。

四、记忆技巧：把代码变成“寻宝游戏”

用场景化记忆法理解最优解法的核心逻辑：

1. 角色赋值

• 哈希表（numSet）：扮演“地图”，标记所有宝藏位置（数字存在）。
• 遍历过程：扮演“探险家”，在地图上寻找宝藏。
• 序列起点：扮演“特殊宝藏”，只有找到它才能开启连续挖掘。

2. 游戏规则

① 探险家拿到地图（哈希表），标记所有宝藏位置。
② 探险家随机站在一个数字位置上，检查：

• 如果左边一格（num-1）没有宝藏，则当前位置是“特殊宝藏”，可开启连续挖掘；
• 如果左边有宝藏，则跳过当前位置（留给左边的宝藏来挖掘）。
  ③ 挖到一个宝藏后，持续向右挖掘（检查 num+1），记录最长连续挖掘长度。

3. 关键记忆点

• 只从序列起点开始挖掘 → 避免重复计数。
• 哈希表快速定位宝藏 → O(1) 查询效率。

五、实战拓展：变种题巩固思路

1. 允许重复元素：原题已自动处理（哈希表去重）。
2. 返回具体序列：在计数时记录起点和终点，最后构造序列。
3. 双向扩展：同时向前（num-1, num-2, ...）和向后扩展，适用于“允许不连续但可排序”的场景。

通过“寻宝游戏”的场景记忆，最优解法的逻辑会变得非常直观。记住：算法的本质是“用合适的数据结构优化操作”，本题中哈希表的作用不仅是存储数据，更是为了快速判断“起点”，从而避免重复计算。多思考这种“筛选起点”的思想，能帮助你解决更多类似问题。