128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

分析

• 当然直接排序，然后寻找最长的长度是可以的，但是复杂度是o(nlgn)，不符合题目要求
• 可以换个思路，假设某个元素作为起点，其他的周边通过哈希集合o(1)的时间复杂度寻找
• 如果每个元素都寻找也是很高的复杂度o(n*n), 所以可以只从窗口第一个位置寻找，这样复杂度就只是o(n)了

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # 哈希的好处在于可以寻找目标值的时候更加快一些
        # 所以可以把所有元素放到哈希集合中，遍历寻找该元素所能扩展的最大长度
        # 注意的点是只需要遍历窗口第一个数字即可，复杂度为o(n)
        
        num_set = set(nums)
        longest_len = 0
        for num in num_set:
            if num - 1 not in num_set:
                cur_longest_len = 1
                cur_num = num

                while cur_num + 1 in num_set:
                    cur_longest_len += 1
                    cur_num = cur_num + 1

                longest_len = max(cur_longest_len, longest_len)
        
        return longest_len