题目描述
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例分析
示例 1
输入: nums = [100,4,200,1,3,2]
输出: 4
最长连续序列是：
[1,2,3,4]
所以答案是 4。
示例 2
输入: nums = [0,3,7,2,5,8,4,6,0,1]
输出: 9
最长连续序列是：
[0,1,2,3,4,5,6,7,8]
所以答案是 9。
解题思路
这道题最关键的要求是：时间复杂度必须是 O(n)。
如果先排序，再去统计连续序列，虽然思路很自然，但排序本身就需要 O(n log n)，不满足题目要求。
所以这题的核心就是：
如何在不排序的情况下，快速判断某个数字的前一个数或后一个数是否存在。
这正是 HashSet 最擅长的事情。
你给出的代码如下：
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> st = new HashSet<>();
for (int num : nums) {
st.add(num);
}
int m = st.size();
int ans = 0;
for (int x : st) {
if (st.contains(x - 1)) {
continue;
}
int y = x + 1;
while (st.contains(y)) {
y++;
}
ans = Math.max(ans, y - x);
if (ans * 2 >= m) {
break;
}
}
return ans;
}
}
这份代码的核心思想非常经典：把所有数字放进 HashSet，然后只从连续序列的起点开始向后枚举。
为什么要用 HashSet
因为 HashSet 可以在平均 O(1) 的时间内判断一个元素是否存在。
比如我们想知道：
-
x - 1是否存在 -
x + 1是否存在 -
x + 2是否存在
如果用数组或者链表来找，每次都要遍历，效率会很低。 但如果用 HashSet，这些判断都可以很快完成。
所以这题第一步就是：
Set<Integer> st = new HashSet<>();
for (int num : nums) {
st.add(num);
}
这样做还有一个额外好处：
自动去重。
因为题目中数组里可能有重复元素，而连续序列只关心某个数是否存在，不关心它出现了多少次。
为什么只从“起点”开始枚举
这是这道题最关键的优化。
假设集合里有这样一段连续序列：
1, 2, 3, 4, 5
如果我们从每个数都开始往后找：
-
从 1 开始找一遍
-
从 2 开始找一遍
-
从 3 开始找一遍
-
从 4 开始找一遍
-
从 5 开始找一遍
那就会有大量重复计算。
所以我们要想办法只从真正的“起点”开始找。
什么叫起点
如果一个数 x 的前一个数 x - 1 不存在，那么 x 就是某个连续序列的起点。
比如：
-
1前面没有0，所以1是起点 -
2前面有1，所以2不是起点 -
3前面有2，所以3不是起点
所以代码里有这句：
if (st.contains(x - 1)) {
continue;
}
意思是：
-
如果
x - 1存在，说明x不是起点 -
那就跳过，避免重复枚举
这样每一段连续序列只会被统计一次。
核心思路总结
这道题可以概括成三步：
-
把所有元素放进
HashSet -
遍历集合中的每个数，只从连续序列的起点开始处理
-
从起点不断向后查找，统计连续长度，并更新答案
代码解析
1. 先把所有数字加入集合
Set<Integer> st = new HashSet<>();
for (int num : nums) {
st.add(num);
}
这里把数组元素放进 HashSet 中，方便后续快速查找。
2. 获取集合大小并初始化答案
int m = st.size();
int ans = 0;
-
m表示去重后的元素个数 -
ans表示当前找到的最长连续序列长度
3. 遍历集合中的每一个数
for (int x : st) {
这里遍历的是集合，不是原数组。 这样可以避免重复数字带来的干扰。
4. 如果不是起点，就跳过
if (st.contains(x - 1)) {
continue;
}
如果 x - 1 存在，说明 x 不是某段连续序列的开头。
比如在序列 1,2,3,4 中：
-
2前面有1 -
3前面有2 -
4前面有3
所以这些点都不需要重新开始统计。
5. 从起点开始向后扩展
int y = x + 1;
while (st.contains(y)) {
y++;
}
从 x + 1 开始，如果集合中存在这个数，就说明连续序列还在延续，于是继续向后找。
直到某个数不存在为止。
比如从 1 开始：
2 存在
3 存在
4 存在
5 不存在
那么连续序列就是 1,2,3,4。
6. 更新答案
ans = Math.max(ans, y - x);
这里为什么是 y - x？
因为 y 已经停在了第一个不存在的位置。
例如：
-
x = 1 -
最后
y = 5
说明连续序列是：
1,2,3,4
长度正好就是：
5 - 1 = 4
7. 剪枝优化
if (ans * 2 >= m) {
break;
}
这是你代码里的一个小优化。
含义是： 如果当前找到的最长连续序列长度已经足够大，大到超过集合元素数的一半，那么继续找下去提升答案的空间已经很有限，可以直接结束。
这个剪枝不是必须的，不写也能通过。 它只是一个额外优化。
示例推演
我们以这个例子来模拟：
nums = [100,4,200,1,3,2]
先放入集合：
st = {100, 4, 200, 1, 3, 2}
遍历到 100
检查 99 是否存在：
99 不存在
说明 100 是起点。
往后找：
-
101不存在
所以这一段长度为：
101 - 100 = 1
更新答案：
ans = 1
遍历到 4
检查 3 是否存在：
3 存在
说明 4 不是起点，跳过。
遍历到 200
检查 199 是否存在：
199 不存在
说明 200 是起点。
往后找：
-
201不存在
长度为 1，答案仍然是 1。
遍历到 1
检查 0 是否存在：
0 不存在
说明 1 是起点。
往后找：
-
2存在 -
3存在 -
4存在 -
5不存在
所以连续序列为：
1,2,3,4
长度为：
5 - 1 = 4
更新答案：
ans = 4
最终返回 4。
为什么这题能做到 O(n)
很多同学第一次看到这里会疑惑：
外层有
for，内层又有while，为什么总复杂度不是O(n^2)？
关键就在于：
每个数字最多只会被“向后扩展”访问一次。
因为我们只从起点开始枚举。
比如序列：
1,2,3,4,5
只有 1 会进入 while，而 2,3,4,5 都不会作为起点再次进入扩展过程。
所以整体来看，每个元素最多只会被处理常数次，总时间复杂度仍然是 O(n)。
和排序解法对比
排序解法
思路：
-
先排序
-
再遍历统计最长连续长度
优点：
-
容易想到
-
逻辑比较直观
缺点：
-
排序需要
O(n log n) -
不满足题目要求的线性时间复杂度
HashSet 解法
思路：
-
用集合快速查找元素是否存在
-
只从起点开始扩展
优点：
-
时间复杂度
O(n) -
自动去重
-
是这道题最经典的解法
缺点：
-
需要一定的哈希思维
-
第一次想到“只从起点开始找”不太容易
复杂度分析
设去重后集合中有 m 个元素。
时间复杂度
O(n)
-
插入
HashSet需要O(n) -
遍历集合并扩展连续序列，整体仍然是
O(n)
所以总时间复杂度是线性的。
空间复杂度
O(n)
需要一个 HashSet 来存储所有元素。
总结
这道题最核心的两个点就是：
-
用
HashSet实现快速查找 -
只从连续序列的起点开始向后扩展
也就是说，真正的关键不是“找连续”，而是：
怎样避免重复地找连续。
只要把这一点想清楚，这道题就不难了。
你可以把这题总结成一句话：
先去重放进集合，再从每段连续序列的起点开始往后数长度。
这是哈希表题里非常经典的一道题，也是一道很能体现“用空间换时间”思想的题目。
