LeetCode LCR 119. 最长连续序列
题目描述
题意分析
找出数组中数值连续的最长序列长度，元素在原数组中的位置和先后顺序不限。重复值不能增加长度，空数组返回 0。题目进阶要求线性时间，下面用哈希集合避免排序。
解法：哈希集合从连续段起点扩展
核心思路
[!blue]
先将所有数放入哈希集合，既去掉重复值，也能快速查询一个数是否存在。不同数值会自然分成若干互不相交的连续段，每段只需从最小值开始数一次；若从每个数都向后扩展，同一段会被反复扫描，最坏退化为平方时间。
判断
num是否为起点，只需查看num - 1是否存在。前驱存在时，它位于某段内部，可以跳过；前驱不存在时，它就是该段唯一的起点。从这里令cur = num、len = 1，不断检查下一数值，存在就同时增加cur和len，直到遇到缺口。从起点出发不会漏掉段首，连续查询又会一直走到段尾，因此得到整段长度。每个连续段都有且只有一个起点，比较所有段长就能得到全局最大值。
外层遍历去重后的集合，每个不同值只判断一次前驱；内层扩展虽然嵌套在外层中，但每个不同值只属于一个连续段，不会被其他起点再次扫描。所有扩展次数合计为线性，这正是哈希法满足进阶时间要求的原因。
解题步骤
- 将全部数加入集合，将答案初始化为 0。
- 遍历集合，跳过前驱已经存在的数。
- 从剩余起点向后逐个扩展，直到下一数值不在集合中。
- 用当前段长更新答案，遍历完后返回最大值。
代码实现
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)$，
n为数组长度。建集合扫描n个元素，前驱判断和全部连续段扩展都只需线性次哈希操作。- 空间复杂度：$O(n)$，集合最多保存
n个不同值。
关键点总结
[!green]
- 哈希集合负责查询与去重，起点判定负责避免重复扫描同一段。
- 必须遍历集合；若遍历原数组，重复起点可能多次触发整段扩展，破坏线性时间。
- 只统计不同数值的个数，与原数组下标顺序无关。
易错点总结
[!yellow]
- 只从没有前驱的值开始向后扩展，遍历集合而不是让重复起点反复扫描。
- 连续长度按不同数值计算，重复元素不增加长度；空数组返回 0。
- 本题数值范围为
[-10^9, 10^9]，加减一不会溢出；不能误认为题面覆盖完整int范围。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！