问题
给定一个未排序的整数数组 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解法
这个问题可以通过使用哈希表（Python 中的set）来解决。核心思想是遍历数组，对于每个元素，检查它减一的元素是否存在于哈希表中，如果存在，则表示找到了一个连续序列的起点，然后继续检查下一个元素是否存在，直到序列被打断。
class Solution: def longestConsecutive(self, nums: List[int]) -> int: # 初始化最长连续序列长度为0 longest_streak = 0 # 将列表转换为集合，以便快速检查元素是否存在 num_set = set(nums) # 遍历集合中的每个数字 for num in num_set: # 如果当前数字的前一个数字不在集合中，说明找到了一个序列的起点 if num - 1 not in num_set: current_num = num current_streak = 1 # 当前一个数字不存在，当前数字序列长度初始化为1 # 从当前数字开始，检查下一个数字是否存在于集合中 while current_num + 1 in num_set: current_num += 1 # 如果存在，更新当前数字为下一个数字 current_streak += 1 # 序列长度加1 # 更新最长连续序列长度 longest_streak = max(longest_streak, current_streak) # 返回最长连续序列长度 return longest_streak实现步骤：
- 定义一个变量
longest_streak来存储遍历过程中找到的最长连续序列的长度，初始值设为 0。 - 将输入列表
nums转换成集合num_set，这样可以通过 O(1) 时间复杂度检查任意数字是否存在于集合中。 - 遍历集合
num_set中的每个数字，对于每个数字，检查其前一个数字（num - 1）是否存在于集合中。如果不存在，说明找到了一个连续序列的起点。 - 从找到的起点开始，通过
while循环检查序列中的下一个数字是否存在于集合中，如果存在，则更新当前数字并增加序列长度。 - 在每次找到一个新的连续序列后，比较并更新
longest_streak变量的值。 - 遍历完成后，返回
longest_streak变量的值，即最长连续序列的长度。
复杂度分析
- 时间复杂度：O(N)，其中 N 是数组
nums的长度。因为每个元素最多被访问两次（一次在初始化num_set时，一次在主循环中）。 - 空间复杂度：O(N)，用于存储哈希表。
