难度: Medium
给定一个未排序的整数数组 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
提示：
0 <= nums.length <= 105-109 <= nums[i] <= 109运行时间: 90 ms
内存: 29.5 MB
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
mySet = set(nums)
maxLen = 0
for i in range(0,len(nums)):
presentLen = 1
if nums[i]-1 in mySet:
continue
while nums[i]+presentLen in mySet:
presentLen+=1
maxLen = max(maxLen,presentLen)
return maxLen
该题解使用了哈希集合来存储所有数组元素，然后遍历数组中的每个数字。对于每个数字，检查其是否可能是连续序列的开始（即检查这个数字的前一个数字是否不在集合中）。如果是序列的开始，则继续检查下一个数字是否存在于集合中，并更新当前序列的长度，直到找不到下一个连续的数字。这样可以确保每个连续序列只被检查一次，从而使算法的时间复杂度为线性。
时间复杂度: O(n)
空间复杂度: O(n)
# 定义解决方案类
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
# 将所有数字存入哈希集合以便快速查找
mySet = set(nums)
# 初始化最长序列长度为0
maxLen = 0
# 遍历数组中的每个元素
for i in range(0, len(nums)):
# 初始化当前连续序列的长度为1
presentLen = 1
# 如果当前数字的前一个数字在集合中，则跳过当前数字
if nums[i]-1 in mySet:
continue
# 检查当前数字之后的连续数字是否存在于集合中
while nums[i]+presentLen in mySet:
# 找到了连续数字，长度增加
presentLen += 1
# 更新最大长度
maxLen = max(maxLen, presentLen)
# 返回最长序列的长度
return maxLen
这一步骤是为了确定当前数字是否是一个连续序列的起始点。如果当前数字的前一个数字也在集合中，这意味着当前数字已经是某个正在考虑的连续序列的一部分，因此不需要再从当前数字开始计算新的序列长度。这种方式确保每个连续序列只被计算一次，从而有效控制算法的时间复杂度保持在O(n)。
在理想情况下，哈希表的时间复杂度为O(1)进行插入和查找操作。然而，实际中可能会因为哈希冲突而降低效率。尽管如此，通过设计良好的哈希函数和调整哈希表的大小，可以将冲突降到最低，从而在大多数情况下接近O(1)的性能。因此，即使考虑到哈希冲突，整个算法在处理n个元素时的总体时间复杂度仍可保持在O(n)。
算法一开始就将所有数组元素存入哈希集合中，集合的性质是不允许重复的元素存在。因此，当从哈希集合中检查元素时，我们已经在一定程度上保证了每个数字只会被考虑一次。这避免了重复的问题，同时也保证了算法的效率。