哈希表

用途：用于快速判断一个元素是否出现在集合里

可以做到O(1)的时间复杂度

哈希函数

哈希碰撞

将两个元素都映射到索引相同的位置，这一现象叫做哈希碰撞。

解决办法

拉链法
线性探测法

练习题

242、有效的字母异位词

Python便捷解法：

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        from collections import Counter
        return Counter(s)==Counter(t)

两个数组的交集

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        set1 = set(nums1)
        set2 = set(nums2)
        return list(set1&set2)

202、快乐数

class Solution:
    def isHappy(self, n: int) -> bool:
        def getnum(n):
            res = 0
            while n:
                n,r = divmod(n,10)
                res+=r**2
            return res
        record = set()
        while True:
            n = getnum(n)
            if n == 1:
                return True
            if n in record:
                return False
            else:
                record.add(n)

1、两数之和

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        myhash = {}
        for index,num in enumerate(nums):
            if target-num in myhash:
                return [index, myhash[target-num]]
            myhash[num] = index

15、三数之和

方法1：使用哈希表

将三数之和问题转换为两数之和。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        for i in range(len(nums)):
            myhash = {}
            # target = -nums[i]
            for j in range(i+1,len(nums)):
                if -nums[i]-nums[j] in myhash:
                    tmp = [nums[i],nums[j],myhash[-nums[i]-nums[j]]]
                    if tmp not in res:
                        res.append(tmp)
                myhash[nums[j]] = nums[j]
        return res