LeetCode 128. 最长连续序列
题目描述
题意分析
在未排序数组中，找出数值连续的一段整数序列，返回它的最大长度。连续指相邻数值相差
1，不要求这些数在原数组中位置相邻，也不要求保留原数组的先后顺序。同一个值出现多次只算一个，负数也可以参与连续序列。题目要求线性时间，不能依赖排序后扫描；需要快速判断某个值是否存在，并避免从同一段里的每个数都重新向后数一遍。空数组的答案为
0。
解法：哈希集合只从序列起点扩展
核心思路
[!blue]
先把所有数加入哈希集合。集合同时完成去重和快速存在性查询，原数组中的位置与出现次数便不再影响判断。接下来在集合中寻找每段连续序列的最小值，只从这些起点扩展。
对一个数
num，如果num - 1也在集合中，它就不是起点，所在连续段应该交给更小的数处理，当前直接跳过。如果前驱不存在，才从num开始依次查找num + 1、再下一个值，直到首次缺失为止，得到这一整段的长度。每一段连续整数恰好有一个没有前驱的最小值，所以只从起点搜索不会遗漏任何一段；同一段中的其他值又都会因存在前驱而跳过，不会重复展开。集合的遍历顺序不重要，因为是否为起点只取决于前驱是否存在，而不取决于谁先被访问。
外层也必须遍历去重后的集合，而不是原数组。否则同一个起点在输入中重复出现时，可能把整段序列反复展开，破坏线性时间。对每个互不相同的数，外层只检查一次前驱；所有向后扩展合起来也只跨过每段一次，因此总工作量是线性的。
用
ans保存已处理连续段的最大长度。代码还在计算前驱和后继前检查整数极值，避免减一或加一溢出后，把整数两端错误地视为相邻。没有元素时不进入循环，初始的0就是答案。
解题步骤
- 将数组元素加入哈希集合，初始化
ans = 0。- 遍历集合中的每个
num；若存在前驱num - 1，跳过它。- 对没有前驱的起点，初始化
cur = num、当前长度为1。- 只要后继
cur + 1存在，就推进cur并增加长度；整数极值处先判断再做加减。- 用这段长度更新
ans，遍历结束后返回最大值。
代码实现
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(n)$，哈希集合最多保存数组中全部不同的值。
关键点总结
[!green]
- 哈希集合同时提供快速查找和去重。
num - 1不存在是连续序列起点的唯一判据。- 只从起点扩展，才能保证所有扩展步数合计为 $O(n)$。
- 计算前驱和后继时要防止整数极值溢出，避免把最小值与最大值误连。
易错点总结
[!yellow]
- 从每个数字都向后扩展，会在长连续序列上退化为 $O(n^2)$。
- 重复值不能增加序列长度，应通过集合去重。
- 排序后扫描虽能求解，但时间复杂度为 $O(n \log n)$，不满足题目要求。
- 空数组应返回
0；答案从0初始化即可自然覆盖。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！