24 - Hard - 最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

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

时间：O(n)，空间O(n)

class Solution:
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        d = {}
        _max = 0
        for i in nums:
            if i not in d:
                left = d.get(i - 1, 0)  # 左边-1的元素的长度值
                right = d.get(i + 1, 0)  # 右边+1的元素的长度值
                d[i] = 1 + right + left  # 当前值改为左右值和+1
                d[i + right] = d[i]  # 关键！！！更新左边序列的最左边元素长度值
                d[i - left] = d[i]  # 关键！！！更新右边序列的最右边元素长度值
                _max = max(_max, d[i])
        return _max