LeetCode 128 最长连续序列：从暴力枚举到 O (n) 最优解法全解析

题目描述

给定一个未排序的整数数组nums，找出数组中数字连续的最长序列的长度，注意序列元素无需在原数组中相邻。题目进阶要求设计并实现时间复杂度 O (n)的算法完成求解力扣 (LeetCode)。

示例与约束

1. 示例 1：输入[100,4,200,1,3,2]，输出4，最长连续序列为[1,2,3,4]；
2. 示例 2：输入[0,3,7,2,5,8,4,6,0,1]，输出9，最长连续序列为[0,1,2...8]；
3. 约束：数组长度范围0 <= nums.length <= 10^5，元素取值范围-10^9 <= nums[i] <= 10^9，数组可能存在重复元素力扣 (LeetCode)。

这是算法刷题与面试中的经典高频题，不少初学者会优先选择排序解法，但排序会带来O(nlogn)的时间复杂度，无法满足题目进阶要求。本文将循序渐进，从最直观的暴力解法开始，一步步优化思路，最终给出符合O(n)复杂度的最优方案。

二、解法一：暴力枚举（直观但低效）

核心思路

遍历数组中的每一个元素，将其视作连续序列的起始值。对于当前元素num，持续检查num+1、num+2…… 是否存在于原数组中，不断累加当前序列的长度。全程记录遍历过程中出现的最大长度，遍历结束后即为答案。

伪代码实现

plaintext

max_len = 0 # 遍历数组所有元素 for num in nums: cur_len = 1 # 向后依次检查连续数字是否存在 while num + 1 在 nums 中: num += 1 cur_len += 1 # 更新全局最长长度 max_len = max(max_len, cur_len) return max_len

方案缺陷

该思路逻辑简单、容易理解，但存在致命的效率问题：时间复杂度为 O (n²)。 举个例子，对于数组[1,2,3,4]：遍历元素1时，会完整遍历整个连续序列；后续遍历2、3、4时，又会重复检查后续连续数字，产生大量冗余计算。当数组数据量达到万级、十万级时，程序运行速度会急剧下降，无法适配大数据场景。

三、核心优化：规避重复计算的关键逻辑

想要优化暴力解法，首先要解决重复遍历连续序列的问题。我们可以提炼出一个核心判定规则：

若数组中不存在num - 1这个数字，那么当前元素num一定是某一条连续序列的真正起点。

基于这个规则，我们就可以跳过所有处于连续序列中间位置的元素，仅针对序列起点去统计长度。从根源上杜绝重复计算，这也是本题优化的核心突破口。

举个例子：数组[100,4,200,1,3,2]。元素1不存在前驱数字0，是序列起点；而元素2存在前驱1、元素3存在前驱2，二者都属于序列中间元素，无需单独遍历统计。

四、解法二：哈希集合（HashSet）最优解（O (n) 时间复杂度）

结合上述优化逻辑，我们引入哈希集合作为核心数据结构。哈希集合有两大优势：一是自动对数组去重（重复元素不影响连续序列统计）；二是元素查询操作的时间复杂度为 O (1)，可以大幅提升查找效率。

完整解题步骤

1. 数据预处理：遍历原数组，将所有元素存入哈希集合，完成去重，同时构建 O (1) 查询的数据源；
2. 遍历哈希集合：逐个判断当前元素是否为连续序列起点（判断集合中是否存在num - 1）；
3. 统计序列长度：若当前元素是起点，则向后循环查询curNum + 1是否存在，累加当前序列长度；
4. 更新结果：每次统计完一条连续序列后，对比并更新全局最长长度；
5. 返回结果：遍历结束后，输出最长连续序列长度。

Java 完整代码

java

运行

import java.util.HashSet; import java.util.Set; public class Solution { public int longestConsecutive(int[] nums) { // 1. 预处理：将数组元素存入哈希集合，完成去重 Set<Integer> numSet = new HashSet<>(); for (int num : nums) { numSet.add(num); } int longestConsecutive = 0; // 2. 遍历哈希集合中的所有元素 for (int num : numSet) { // 判定：当前元素是连续序列的起点 if (!numSet.contains(num - 1)) { int curNum = num; int curLen = 1; // 向后延伸，统计当前连续序列的长度 while (numSet.contains(curNum + 1)) { curNum = curNum + 1; curLen++; } // 更新全局最长长度 longestConsecutive = Math.max(longestConsecutive, curLen); } } return longestConsecutive; } }

代码逐行解析

1. 哈希集合初始化：HashSet自动剔除数组中的重复值，避免重复元素干扰序列统计；
2. 起点判断：!numSet.contains(num - 1)是核心逻辑，仅对序列起点执行长度统计；
3. 序列延伸：while循环不断向后查找连续数字，直到序列中断，记录当前序列长度；
4. 结果更新：每次完成一条序列统计后，用Math.max保留全局最大值。

时空复杂度分析

1. 时间复杂度 O (n)：每个元素最多被访问两次（一次存入哈希集合，一次参与遍历 / 序列延伸），整体为线性遍历，满足题目进阶要求；
2. 空间复杂度 O (n)：哈希集合需要存储数组全部元素，额外空间与原数组长度成正比。

五、案例实战演示

以输入nums = [100,4,200,1,3,2]为例，模拟代码执行流程：

1. 哈希集合存储结果：{100, 4, 200, 1, 3, 2}；
2. 遍历元素100：集合中无99，判定为起点。向后查询101不存在，序列长度为 1，全局最长长度 = 1；
3. 遍历元素4：集合中存在3，属于序列中间元素，直接跳过；
4. 遍历元素200：集合中无199，判定为起点。向后查询201不存在，序列长度为 1，全局最长长度保持 1；
5. 遍历元素1：集合中无0，判定为起点。依次查询2、3、4均存在，序列长度累加到 4，全局最长长度更新为 4；
6. 遍历元素3、2：二者均存在前驱数字，直接跳过；
7. 最终返回结果4，与题目示例一致。

边界场景适配

1. 空数组：直接返回 0；
2. 单元素数组：序列长度固定为 1；
3. 全重复数组（如[2,2,2]）：去重后仅保留一个元素，返回 1。

六、解题总结与拓展技巧

1. 本题核心考点

• 数据结构选型：当题目需要频繁判断元素是否存在时，优先使用哈希集合、哈希表等查询效率为 O (1) 的结构，规避数组遍历查询的高耗时问题；
• 逻辑剪枝优化：通过「判断前驱数字是否存在」筛选序列起点，剪掉中间元素的无效遍历，是算法优化中典型的逻辑剪枝思路；
• 复杂度把控：主动规避排序（O (nlogn)）等低效方案，紧扣题目 O (n) 的复杂度要求。

2. 同类题目拓展

该「判定序列起点 + 哈希查询」的思路可复用在各类连续数字统计类题目中。在刷题过程中，遇到未排序数组的连续区间、连续数字统计问题，都可以优先考虑这套解题框架。

3. 学习建议

对于初学者，建议先手写暴力解法理解题意，再逐步思考「哪里存在重复计算、如何剪枝」，最后结合哈希结构完成优化。循序渐进地推导，才能真正吃透算法背后的思维逻辑，而非单纯背诵代码。

七、补充说明

部分同学会选择「先排序再遍历」的解法，这种方式代码简单，但排序操作会带来 O (nlogn) 的时间复杂度，无法满足本题 O (n) 的进阶要求，仅能作为基础练习方案。在面试场景中，面试官通常会要求实现线性时间复杂度解法，因此基于哈希集合的方案是本题的最优解与标准答案。