最长连续序列的长度LongestConsecutive

问题

给定一个未排序的整数数组 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

实现步骤：

1. 定义一个变量longest_streak来存储遍历过程中找到的最长连续序列的长度，初始值设为 0。
2. 将输入列表nums转换成集合num_set，这样可以通过 O(1) 时间复杂度检查任意数字是否存在于集合中。
3. 遍历集合num_set中的每个数字，对于每个数字，检查其前一个数字（num - 1）是否存在于集合中。如果不存在，说明找到了一个连续序列的起点。
4. 从找到的起点开始，通过while循环检查序列中的下一个数字是否存在于集合中，如果存在，则更新当前数字并增加序列长度。
5. 在每次找到一个新的连续序列后，比较并更新longest_streak变量的值。
6. 遍历完成后，返回longest_streak变量的值，即最长连续序列的长度。

复杂度分析

• 时间复杂度：O(N)，其中 N 是数组nums的长度。因为每个元素最多被访问两次（一次在初始化num_set时，一次在主循环中）。
• 空间复杂度：O(N)，用于存储哈希表。