LeetCode 128. 最长连续序列
目录
题目描述
题意分析
给定一个未排序的整数数组，找出数值上连续（如
1,2,3,4）的最长序列长度——注意是数值连续，与元素在数组中的位置完全无关，这一点和「最长递增子序列」那类看位置顺序的题有本质区别。题面明确要求 $O(n)$ 时间，这是最强的约束信号：它直接把「先排序再扫一遍」排除在标准答案之外——排序至少 $O(n \log n)$，写出来等于答非所问。反过来想，$O(n)$ 的要求也在提示我们要用能常数时间判存在性的结构。
边界与细节：数组可能为空，此时返回
0；数组中可能有重复元素，重复值对连续长度没有任何贡献（[1,2,2,3]的答案是3不是4）；元素范围覆盖int的最小值到最大值，涉及num ± 1的运算要留意溢出。
解法：哈希集合只从序列起点扩展
核心思路
将所有数字放入哈希集合。只有当
num - 1不在集合中时，num才是一段连续序列的起点；从这些起点向后查找num + 1，即可避免重复扫描同一段序列。
解题步骤
- 将数组元素加入哈希集合，完成去重并支持常数时间查找。
- 遍历集合；若
num - 1存在，说明num不是起点，直接跳过。- 从起点不断查找下一个连续数字，统计当前序列长度。
- 用每段序列的长度更新最大值。
代码实现
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>();
for (int num : nums) {
set.add(num);
}
int ans = 0;
for (int num : set) {
if (num != Integer.MIN_VALUE && set.contains(num - 1)) {
continue;
}
int cur = num;
int len = 1;
while (cur != Integer.MAX_VALUE && set.contains(cur + 1)) {
cur++;
len++;
}
ans = Math.max(ans, len);
}
return ans;
}
}
import "math"
func longestConsecutive(nums []int) int {
set := make(map[int]bool)
for _, num := range nums {
set[num] = true
}
ans := 0
for num := range set {
if num != math.MinInt && set[num-1] {
continue
}
cur := num
length := 1
for cur != math.MaxInt && set[cur+1] {
cur++
length++
}
if length > ans {
ans = length
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，哈希查找均摊为 $O(1)$，每段连续序列只从起点完整扫描一次。
- 空间复杂度：$O(n)$，用于保存哈希集合。
关键点总结
- 哈希集合同时提供快速查找和去重。
num - 1不存在是连续序列起点的唯一判据。- 只从起点扩展，才能保证所有扩展步数合计为 $O(n)$。
- 计算前驱和后继时要防止整数极值溢出，避免把最小值与最大值误连。
易错点总结
- 从每个数字都向后扩展，会在长连续序列上退化为 $O(n^2)$。
- 重复值不能增加序列长度，应通过集合去重。
- 排序后扫描虽能求解，但时间复杂度为 $O(n \log n)$，不满足题目要求。
- 空数组应返回
0；答案从0初始化即可自然覆盖。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| LCR 119. 最长连续序列 | 中等 | 本题的 LCR 镜像题，同一套代码 |
| 674. 最长连续递增序列 | 简单 | 要求位置连续，一次线性扫描即可 |
| 485. 最大连续 1 的个数 | 简单 | 统计最长连续段的最简形态，计数器归零技巧 |
| 300. 最长递增子序列 | 中等 | 保持相对位置但可不连续，需动态规划或贪心加二分 |
| 298. 二叉树最长连续序列 | 中等 | 连续序列搬到树上，沿父子链递归传递长度 |
| 549. 二叉树最长连续序列 II | 中等 | 允许递增递减双向，路径可跨越父节点 |