最长连续序列
Longest Consecutive Sequence
本机进度仅保存在当前浏览器
题目描述
给定一个未排序的整数数组 nums，找出数字连续的最长序列（如 1, 2, 3, 4）的长度。不要求序列元素在原数组中连续。请设计 O(n) 的算法。
示例：nums = [100, 4, 200, 1, 3, 2]，最长连续序列为 [1, 2, 3, 4]，输出 4。
解题思路
- 排序后扫描是 O(n log n)，达不到要求；用哈希集合把"查某个数在不在"降到 O(1)。
- 关键去重技巧：只有当 x - 1 不在集合中时，x 才是某条连续序列的起点，只从起点向后数。
- 这样每条序列只被完整遍历一次，所有元素总访问次数仍是 O(n)，避免了重复计数导致的 O(n^2)。
参考实现
查看参考实现Python · 建议先自行作答
def longestConsecutive(nums):
num_set = set(nums)
best = 0
for x in num_set:
# 只从序列起点向后统计
if x - 1 in num_set:
continue
cur = 1
while x + cur in num_set:
cur += 1
best = max(best, cur)
return best