哈希表理论基础

代码随想录 (programmercarl.com)

• 当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

242. 有效的字母异位词 - 力扣（LeetCode）

解题思路

• 用一个哈希表，先记录s中字母出现次数，然后如果t中出现一样字母就-1，最后如果哈希表中存在非0值，则返回false；
• 也可以直接调用函数

方法一

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        if len(s) != len(t):
            return  False

        hashtable = {}
        for i in s:
            if i in hashtable:
                hashtable[i] += 1
            else:
                hashtable[i] = 1

        for i in t:
            if i in hashtable:
                hashtable[i] -= 1

        for i in hashtable:
            if hashtable[i] != 0:
                return False
        return True

方法二

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:

        from collections import Counter
        s = Counter(s)
        t = Counter(t)

        return s==t

349. 两个数组的交集 - 力扣（LeetCode）

直接用set

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:

        return list(set(nums1) & set(nums2))

• 还是没明白什么时候用数组，什么时候用set：如果范围可控、数字不大，可用数组
• "如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费！" ???

202. 快乐数 - 力扣（LeetCode）

class Solution(object):
    def isHappy(self, n):
        """
        :type n: int
        :rtype: bool
        """
        hashtable = {}

        while True:
            n_temp = 0
            for ch in str(n):
                n_temp += int(ch)**2
            n = n_temp

            if n == 1:
                return True
            
            if n in hashtable:
                return False
            else:
                hashtable[n] = 0

• 用set、hashtable都行

1. 两数之和 - 力扣（LeetCode）

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hashtable = {}
        for index, value in enumerate(nums):
            if target-value in hashtable:
                return [hashtable[target-value], index]
            else:
                hashtable[value] = index
       

• 还可以深挖，埋个坑