128 Longest Consecutive Sequence
128. Longest Consecutive Sequence
题目: https://leetcode.com/problems/longest-consecutive-sequence/
难度:
Hard
思路
首先去重复，时间O(N),然后将所有元素都放到一个字典中，这样判断一个数字的后续在不在这个字典中，如果存在就一直判断下去，每次判断只要O(1)。
对于每个数，如果他的前续已经判断过了，他就没有必要判断了，继续判断下一个数，即：
if num - 1 in nums:
continue
AC代码：
class Solution(object):
def longestConsecutive(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
nums = set(nums)
tmp = {}
for num in nums:
tmp[num] = 1
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
但其实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内部“不会有重复元素”。
因此，代码也可以写成这样
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
