哈希表的思考

在python中有个函数是set（）

a = [1,43,2,4,3,54]
a = set(a)
> a = {1,2,3,4,54,43}

输出的是一个无序的不重复的集合，其实就是我们题目所说的哈希表。

这个函数有啥用？或者说这个哈希表有啥用？

为了快速找到相应的值

那这个快速找到相应的值有啥用呢？其实就是牺牲了空间换时间，在O(1)的时间内，快速找到对应的值

a = [29,1,3,2,4,65,456,45,37,98,65,44,76,1233,435,6657,345325,34523,6545,3334,556]
b = set(a)

import time
t1 = time.time()
if 3 in a:
    print('true')
t2 = time.time()

t3 = time.time()
if 3 in b:
    print('true')
t4 = time.time()
delta1 = int(t2*1000000)-int(t1*1000000)
delta2 = int(t4*1000000)-int(t3*1000000)
print('list cost:',delta1,'set cost:', delta2)

>  list cost:1219 set cost:219

可以看出同样查找 set 内快很多

leetcode #128(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.

def longestConsecutive(self, nums):
    nums = set(nums)
    best = 0
    for x in nums:
        if x - 1 not in nums:
            y = x + 1
            while y in nums:
                y += 1
            best = max(best, y - x)
    return best