D5|哈希表，善用数据结构

哈希表理论基础

1.数组也是哈希表

1）数组的下标索引1、2、3就是哈希表中的关键码

2）哈希表将数据通过哈希函数计算哈希值，并通过求模等处理映射到有范围的索引，并在该索引位置存放对应的值，从而提高查询效率

3）哈希表都是用来快速判断一个元素是否出现集合里，常见哈希结构有数组、集合、字典

2.集合和字典的用法还不太熟悉！

练习

● 242.有效的字母异位词

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        res1, res2 = {}, {}
        for u in s:
            if u not in res1.keys():
                res1[u] = 1
            else:
                res1[u] += 1
        # print(res1)
        for v in t:
            if v not in res2.keys():
                res2[v] = 1
            else:
                res2[v] += 1
        # print(res2)
        if res1 == res2:
            return True
        else:
            return False
           

优化：可以用数组记录字母的ascii码（索引），且只用一个数组

● 349. 两个数组的交集

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        s1 = set(nums1)
        s2 = set(nums2)
        s = s1 & s2
        res = []
        for u in s:
            res.append(u)
        return res
           

集合的交& 并| 差- 补^

● 202. 快乐数

复习前：

1）没看到无限循环，看成了会变成无穷大……

2）居然连求得每个数位都不会 哇呜 我哭了才怪~

class Solution:
    def isHappy(self, n: int) -> bool:
        # 关键词无限循环，所以得判断是否进入了循环
        # 哇呜 我连取余也不会！
        # a = float('inf')
        s = set()
        while n not in s:
            s.add(n)
            t, k = 0, 1
            while n:
                t += (n % 10) ** 2
                n = (n // 10)
            if t == 1:
                return True
            n = t
        return False
           

其实还可以用快慢指针哦！

● 1. 两数之和

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        a = defaultdict(int)
        for index, value in enumerate(nums):
            if value not in a.keys():
                a[value] = index
        for i, u in enumerate(nums):
            if target - u in a.keys() and i != a[target - u]:
                return [i, a[target - u]]
           

总结

难在底层原理，重点在什么时候用哈希表