题目
给定一个未排序的整数数组 nums，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9示例 3：
输入：nums = [1,0,1,2]
输出：3提示
一句话思路：用哈希集合去重后，只从「连续序列的起点」开始向后延伸，跳过不是起点的数字，保证整体 O(n)。
- 先把
nums转成集合st，去重 + O(1) 查存在。 - 怎么判断起点：当前数字
x如果存在x - 1，说明它不是起点，直接跳过（否则同一个序列会被重复数）。 - 从起点开始用
while向后找连续的下一个数，更新最长长度。 - 为什么是 O(n)：每个数字最多被「进入序列」和「延伸」各访问一次，整体线性。
答案
python
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
st = set(nums) # 转成集合：去重，且 O(1) 判断某数是否存在
ans = 0 # 记录最长连续序列的长度
for x in st: # 遍历集合中的每个数
if x - 1 in st: # 存在前驱 x-1，说明 x 不是序列起点
continue # 跳过，避免同一个序列被重复统计
y = x + 1 # 从起点 x 的下一个数开始
while y in st: # 只要下一个数存在，就继续延伸
y += 1 # 延伸：判断再下一个数
ans = max(ans, y - x) # 当前序列长度是 y-x，更新最大值
return ans # 返回最长长度
留言板