leetcode128.最长连续序列

题目：

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

思路：

哈希表

建立一个空字典，然后字典中存放每个数当前对应的连续空间的长度，遍历到一个数就计算它对应的连续长度。看这个数左边相邻的数在不在，如果不在默认为0,右边同理，如果相邻的数在哈希表中，那读取到的值就是相邻的数对应的空间长度，当前数对应的空间长度就是左长度加右长度加1,那对于左边界来说，就是左边相邻数的连续空间长度的左边界对应的长度长了，同理右边相邻数的连续空间长度的右边界对应的长度也变长了，因为都和当前这个数连上了。所以要更新除当前值外两个边界的长度，然后更新长度的最大值，返回结果。

遍历到这个数后，先判断这个键在哈希表中是否存在，以此去掉重复的元素。

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dict1 = dict()
        res = 0
        for num in nums:
            if num not in dict1:
                l = dict1.get(num - 1,0)
                r = dict1.get(num + 1,0)
                curl = 1 + l + r 
                dict1[num] = curl
                dict1[num - l] = curl
                dict1[num + r] = curl
                if curl > res:
                    res = curl
        return res 
        # set()生成无序不重复元素集合
        # 时间和空间复杂度都是O(n)