128. 最长连续序列

128. 最长连续序列

• 0 <= nums.length <= 105

• 109 <= nums[i] <= 109

解题思路

算法步骤

1. 首先将所有数字存入哈希表中，这样我们可以O(1)时间内判断一个数字是否存在

2. 遍历哈希表中的每个数字x，如果x-1不在哈希表中，说明x是一个连续序列的起点

3. 从x开始，不断查找x+1, x+2, ...是否存在于哈希表中，直到找不到为止

4. 记录当前连续序列的长度，并更新最长连续序列的长度

代码解析

• unordered_set<int> set; - 创建哈希表用于存储数组中的数字

• for(auto num : nums) set.insert(num); - 将所有数字插入哈希表

• if(set.contains(x) && !set.contains(x - 1)) - 判断当前数字是否为连续序列的起点

• while(set.contains(y + 1)) y++; - 向后查找连续的数字

• res = max(res, y - x + 1); - 更新最长连续序列的长度

复杂度分析

• 时间复杂度：O(n)。虽然有两层循环，但内层循环最多执行n次，因为每个数字最多被访问一次。

• 空间复杂度：O(n)，需要哈希表存储所有数字。