html5网站建设基本流程,公司设计图图片简笔画,网站百度优化,网站管理系统排名最长连续序列 给定一个未排序的整数数组 nums #xff0c;找出数字连续的最长序列#xff08;不要求序列元素在原数组中连续#xff09;的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1#xff1a; 输入#xff1a;nums [100,4,200,1,3,2] 输出找出数字连续的最长序列不要求序列元素在原数组中连续的长度。 请你设计并实现时间复杂度为 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
对于数组中存在的连续序列为了统计每个连续序列的长度我们希望直接定位到每个连续序列的起点从起点开始遍历每个连续序列从而获得长度。
那么如何获取到每个连续序列的起点呢或者说什么样的数才是一个连续序列的起点 答案是这个数的前一个数不存在于数组中因为我们需要能够快速判断当前数num的前一个数num - 1是否存在于数组中。
同时当我们定位到起点后我们就要遍历这个连续序列什么时候是终点呢 答案是当前数num的后一个数nunm 1不存在于数组中因此我们需要能够快速判断当前数num的后一个数num 1是否存在于数组中。
为了实现上述需求我们使用哈希表来记录数组中的所有数以实现对数值的快速查找。
python
class Solution:def longestConsecutive(self, nums: List[int]) - int:res 0 # 记录最长连续序列的长度num_set set(nums) # 记录nums中的所有数值for num in num_set:# 如果当前的数是一个连续序列的起点统计这个连续序列的长度if (num - 1) not in num_set:seq_len 1 # 连续序列的长度初始为1while (num 1) in num_set:seq_len 1num 1 # 不断查找连续序列直到num的下一个数不存在于数组中res max(res, seq_len) # 更新最长连续序列长度return res
