最长连续序列

LeetCode 最长连续序列题解，利用集合实现 O(n) 时间复杂度，通过判断序列起点避免重复遍历。

Leetcode 哈希表 python

题目

https://leetcode.cn/problems/longest-consecutive-sequence/description/?envType=study-plan-v2&envId=top-100-liked

解法

思路

第一时间想到排序，但题目要求时间复杂度为O(n)，排序只能做到O(nlogn)。因此还是有条件的依次计数。

因为只需要知道某一个数是否存在在该数组中，不需要知道该数在数组中的位置。因此可以使用集合，查询元素是否在集合中的时间复杂度为O(1)，其本质还是哈希表。

但若对数组内所有数都进行遍历，在极端情况（数组内所有数都是连续的）下，时间复杂度为O(n^2)。因此，对是否为连续序列开头的数还要做一个判断，若非开头数即可跳过，因为已经被覆盖了。

这样，在遍历数组和计数的时间就得到平衡了。

答案

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        nums_set = set(nums) # 转成集合，顺便去重
        res = 0
        for nums in nums_set:
            
            # 找连续序列开头的数
            if nums - 1 in nums_set:
                continue
            count = 1
            while nums + 1 in nums_set:
                nums += 1
                count += 1
            res = max(count, res)
        return res

注意，res初始值必须为0，不能默认为1，因为有可能数组为空。 count可以为1，因为一旦进入则表示至少有一个数组。

收获

在需要查询元素，但不需要值的时候，可以使用集合这个数据结构，查询的时间复杂度为O(1)