LeetCode LCR 119. 最长连续序列
目录
题目描述
题意分析
给定一个未排序的整数数组，找出数值上连续（如
1,2,3,4）的最长序列长度——注意是数值连续，与元素在数组中的位置完全无关，这一点和「最长递增子序列」那类看位置顺序的题有本质区别。题面明确要求 $O(n)$ 时间，这是最强的约束信号：它直接把「先排序再扫一遍」排除在标准答案之外——排序至少 $O(n \log n)$，写出来等于答非所问。反过来想，$O(n)$ 的要求也在提示我们要用能常数时间判存在性的结构。
边界与细节：数组可能为空，此时返回
0；数组中可能有重复元素，重复值对连续长度没有任何贡献（[1,2,2,3]的答案是3不是4）；元素范围覆盖int的最小值到最大值，涉及num ± 1的运算要留意溢出。
解法：哈希集合只从序列起点扩展
核心思路
暴力做法是：对每个数字
num，不断查询num + 1、num + 2是否在数组里，统计以它开头的连续段长度。就算把「是否存在」的查询用哈希集合降到 $O(1)$，仍有一个致命瓶颈：一段长为 $k$ 的连续序列[1..k]，从1开始扩展要走 $k$ 步，从2开始要走 $k-1$ 步……同一段被反复扫描，总代价 $O(k^2)$，全[1..n]的用例直接退化成 $O(n^2)$。关键观察是：一段连续序列的完整长度，只需要从它的最小值（起点）量一次，从中间任何位置出发量到的都是残段，纯属浪费。而「是不是起点」有一个 $O(1)$ 的判据：
num是某段的起点，当且仅当num - 1不在集合中。于是得到本解法的核心不变量：只对满足「
num - 1不在集合中」的数字发起扩展。它为什么能把总量压到 $O(n)$？把所有操作分成两类看——第一类是对每个数字做一次「前驱是否存在」的判定，共 $n$ 次；第二类是扩展中的contains(cur + 1)命中，每命中一次就有一个数字被纳入某段序列，而每个数字只属于唯一一段、这段又只从唯一的起点被扫描一次，所以命中总数也不超过 $n$。也就是说，每个元素恰好被「起点判定」和「被扩展纳入」这两类操作各碰一次，双重循环的总工作量是 $2n$ 级别，均摊下来就是线性。具体流程：先把所有数字倒进哈希集合（顺带去重），再遍历集合，跳过所有非起点，只在起点处向后逐一扩展
cur + 1，用得到的段长更新答案。
解题步骤
- 将数组所有元素加入哈希集合。为什么：后续需要大量「某个值是否存在」的查询，集合把每次查询降到 $O(1)$，同时天然去重，重复元素不会干扰长度统计。
- 遍历集合（而非原数组）中的每个数字。为什么：遍历集合可以让重复值只被判定一次；遍历原数组也对，但重复元素会做无意义的重复判定。
- 若
num - 1存在于集合中，直接跳过。为什么：说明num处在某段序列的中间或末尾，它所在段的完整长度会由该段真正的起点负责统计，从这里扩展只能得到残段。- 否则
num是一段序列的起点，用cur从num出发不断检查cur + 1是否在集合中，在则cur与长度同步加一。为什么：从起点向后走到断裂处，走过的步数恰好就是这段序列的完整长度。- 每段扩展结束后用段长更新答案，遍历完返回。为什么：题目要的是所有段中的最大值，每个起点各贡献一个候选。
以
[100,4,200,1,3,2]走一遍：建集合{100,4,200,1,3,2}。逐个判定起点——100：99不在集合，是起点，101不在，段长1，ans = 1；4：3在集合中，不是起点，跳过；200：199不在，是起点，201不在，段长1，ans仍为1；1：0不在，是起点，依次发现2、3、4都在集合中，5不在，段长4，ans = 4；3、2：前驱都在集合中，跳过。整段1,2,3,4只被起点1完整扫描了一次，最终返回4。
代码实现
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;
}
}
func longestConsecutive(nums []int) int {
set := make(map[int]bool)
for _, num := range nums {
set[num] = true
}
ans := 0
for num := range set {
if set[num-1] {
continue
}
cur := num
length := 1
// 只从连续段起点扩展，每段序列只会被完整扫描一次。
for set[cur+1] {
cur++
length++
}
if length > ans {
ans = length
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$。凭什么：表面上是「遍历套 while」的双重循环，但用均摊论证看——外层对每个不同数字做一次前驱判定，共 $O(n)$；内层 while 每前进一步就把一个数字纳入它所属的唯一段，而每段只从唯一的起点被扫描一次，所以所有 while 步数加起来也不超过 $n$。每个元素恰被「起点判定」与「被扩展纳入」两类操作各碰一次，总量 $2n$，即 $O(n)$。建集合本身也是 $O(n)$。
- 空间复杂度：$O(n)$。凭什么：哈希集合最多保存 $n$ 个不同数字，除此之外只用常数个变量。
关键点总结
- 看到「未排序 + 要求 $O(n)$」的组合，第一反应应当是拿空间换时间：哈希结构把存在性查询压到 $O(1)$，这是绕开排序的通用手段。
- 「只从起点扩展」是一个可迁移的去重思想：当多个元素会重复触发同一段计算时，选一个唯一代表（这里是段的最小值）来承担全部计算，其余元素一律跳过。
- 双重循环不一定是 $O(n^2)$，要看内层的总步数——均摊分析的核心是「给每步操作找到唯一买单的元素」，这套论证在单调栈、滑动窗口里反复出现。
- 重复元素放入集合即自然去重，不需要任何特判；分析题意时先确认重复对答案无贡献，能省掉一类边界代码。
- 面试视角：这题的考点几乎全在复杂度论证上——面试官大概率追问「你这不是两层循环吗，为什么是 $O(n)$」，必须能当场讲清上面的均摊账；先说排序解法再主动指出它不满足要求、引出哈希解法，是稳妥的表达路径。
易错点总结
- 错误写法：不做起点判定，对每个元素都向后（或向两边）扩展——用例
[1,2,3,...,n]，从每个位置都把剩余整段扫一遍，总步数 $1+2+\cdots+n$，退化成 $O(n^2)$，大数据量直接超时；这正是本题设置 $O(n)$ 要求想卡掉的写法。- 错误写法：图省事用排序解法当主解——用例上能得到正确答案，但复杂度是 $O(n \log n)$，题目白纸黑字要求 $O(n)$，面试中等于答非所问，会被直接追问或降档。
- 错误写法：起点判定写反，写成「
num + 1不存在才扩展」再向前找num - 1——逻辑对称本身能得出正确答案，但若和向后扩展混写（判num - 1却仍向num - 1方向扩展）——用例[1,2,3]，每个数都被判为非起点或扩展方向错误，答案输出1。- 错误写法：忘记处理空数组，直接取第一个元素初始化——用例
[]，数组越界或返回1，正确答案是0；把ans初始化为0即可自然覆盖。- 错误写法：以为重复元素会拉长序列，用计数而不是集合——用例
[1,2,2,3]，答案算成4，正确答案是3；连续序列按数值算，重复值无贡献。- 错误写法：在 Java 中不设防地计算
num - 1与cur + 1——用例含Integer.MIN_VALUE或Integer.MAX_VALUE时发生回绕，Integer.MAX_VALUE + 1变成最小值，可能误判存在性甚至死循环；代码中先短路判断num != Integer.MIN_VALUE、cur != Integer.MAX_VALUE再做加减。- 错误写法：内层扩展时只移动
cur忘记累加len（或反之）——用例[1,2,3,4]，返回1或死循环；cur与len必须同步更新。- 错误写法：遍历原数组且不判起点、只用
while里删除元素来防重扫，但删除时机不对——用例[3,2,1]，先访问3时1、2还在集合里却从3起扫不到它们，若又把3删掉，轮到1扩展时段被截断，答案偏小。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 674. 最长连续递增序列 | 简单 | 要求位置连续，一次线性扫描即可 |
| 485. 最大连续 1 的个数 | 简单 | 统计最长连续段的最简形态，计数器归零技巧 |
| 300. 最长递增子序列 | 中等 | 保持相对位置但可不连续，需动态规划或贪心加二分 |
| 298. 二叉树最长连续序列 | 中等 | 连续序列搬到树上，沿父子链递归传递长度 |
| 549. 二叉树最长连续序列 II | 中等 | 允许递增递减双向，路径可跨越父节点 |