【Leetcode】最长连续序列

1 题目给定一个未排序的整数数组 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]输出32 题目分析2.1 难点本题的难点在于要求时间复杂度O(n)。因此不能用数组因为数组不保证有序如果从无序数组的每个元素往左右扩会导致外循环内循环某些元素会被重复计算从而时间复杂度超过O(n);而对数组排序虽然会减少重复计算但也会导致时间复杂度超过O(n);需要抓住那个决定性观察“连续数组”为什么“连续”是因为它的中间不存在缺口。换句话说我们只需要从开头开始计数就可以得到该数组的长度而不需要中间重复工作。理解了这一点就可以解决上面说到的【某些元素会被重复计算】的问题如果 num-1在就不需要计数因为从num开始一定不是最长的。需要考虑到重复元素的问题如果数组中有重复元素即使num-1不在也有可能重复计数相同的起点会被算两遍。因此需要使用set去重。2.2 算法手推有了解题思路之后不要急着写代码而是先用一个例子手推。nums[100,4,200,1,3,2]set{100,4,200,1,3,2}# 开始循环x100:x-199不在起点100x1101不在cur_len1x4:x-13在skip x200:x-1199不在起点200x1201不在cur_len1x1:x-10不在起点1x12在x23在x34在x45不在cur_len4x3:x-12在skip x4:x-13在skip longest_len43 代码代码的关键有三点重复元素的跳过num_set set(num)for num in num_set非起点的跳过if num-1 in num_set则跳过起点的计数while num1 in num_setdeflongestConsecutive(self,nums):num_setset(nums)longest_len0fornuminnum_set:ifnum-1notinnum_set:cur_numnum cur_len1whilecur_num1innum_set:cur_num1cur_len1longest_lenmax(longest_len,cur_len)returnlongest_len