问题给定一个未排序的整数数组 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)用于存储哈希表。