0128._Longest_Consecutive_Sequence.md

128. Longest Consecutive Sequence

难度: Hard

刷题内容

原题连接

• https://leetcode.com/problems/longest-consecutive-sequence/

内容描述

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Example:

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

首先去重复，时间O(N),然后将所有元素都放到一个字典中，这样判断一个数字的后续在不在这个字典中，如果存在就一直判断下去，每次判断只要O(1)。

对于每个数，如果他的前续已经判断过了，他就没有必要判断了，继续判断下一个数，即：

if num - 1 in nums:
    continue

beats 97.28%

class Solution:
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = set(nums)
        lookup = {}
        for num in nums:
            lookup[num] = 1
        res = 0
        for num in nums:
            if num - 1 not in lookup:
                y = num + 1
                while y in lookup:
                    y += 1
                res = max(res, y - num)
        return res

但其实set和字典的in判断都是O(1)

dict与set实现原理是一样的，都是将实际的值放到list中。唯一不同的在于hash函数操作的对象，对于dict，hash函数操作的是其key，而对于set是直接操作的它的元素，假设操作内容为x，其作为因变量，放入hash函数，通过运算后取list的余数，转化为一个list的下标，此下标位置对于set而言用来放其本身，而对于dict则是创建了两个list，一个list该下表放此key，另一个list中该下标方对应的value。参考python dict与set 的实现

其中，我们把实现set的方式叫做Hash Set，实现dict的方式叫做Hash Map/Table(注：map指的就是通过key来寻找value的过程)

set和dict的唯一区别仅在于没有存储对应的value，但是，set的原理和dict一样，所以，同样不可以放入可变对象，因为无法判断两个可变对象是否相等，也就无法保证set内部“不会有重复元素”。

因此，代码也可以写成这样

因为此时nums已经是一个set了，查找也是O(1)了

class Solution(object):
    def longestConsecutive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums = set(nums)
        res = 0
        for num in nums:
            if num - 1 not in nums:
                y = num + 1
                while y in nums:
                    y += 1
                res = max(res, y - num)
        return res