哈希表

本文是面试经典 150 题哈希表问题的详细解读。 LeetCode 上有很多哈希表问题，这里简单介绍一下哈希表和一些常见的哈希表问题。

哈希表是一种基于哈希函数实现的数据结构，可以用于高效地存储和查找键值对。它将键通过哈希函数映射到一个桶中，然后在桶中存储对应的值。

哈希表的实现原理是将键映射为一个整数，这个整数称为哈希值。哈希值通常是一个较小的整数，通常是一个非负整数。然后将哈希值映射到一个桶中，桶是一个数据结构，可以存储一个或多个键值对。

哈希函数是哈希表的核心，它将键映射为哈希值。好的哈希函数应该具有良好的散列性质，即不同的键应该被映射到不同的哈希值，而相同的键应该被映射到同一个哈希值。如果哈希函数不好，可能会导致键映射到同一个桶中，这就会影响哈希表的性能。

当我们要在哈希表中查找一个键时，先将键通过哈希函数计算出哈希值，然后根据哈希值找到对应的桶，然后在桶中查找对应的值。由于哈希函数具有良好的散列性质，我们可以期望在平均情况下，查找键的时间复杂度为 O(1)。

在实际应用中，哈希表常常用于高效地存储和查找大量的数据，比如搜索引擎的索引、数据库的索引等。哈希表也常常用于解决一些算法问题，比如 LeetCode 上的哈希表问题。

Python 中提供了几个常用的哈希表实现库，包括：

• dict：Python 内置的字典类型，基于哈希表实现。可以用来存储键值对，支持常数时间的插入、删除和查找操作。

• collections.defaultdict：基于 dict 类型实现的一个字典子类，可以自动给不存在的键设置默认值。比如，当我们访问一个不存在的键时，可以指定默认值为 0，这样就可以避免 KeyError 异常。以下是一个示例：

  from collections import defaultdict
  
  my_dict = defaultdict(int)
  my_dict['apple'] += 1
  my_dict['banana'] += 2
  print(my_dict)  # 输出 defaultdict(<class 'int'>, {'apple': 1, 'banana': 2})
  

• collections.Counter：也是基于 dict 类型实现的一个字典子类，用于统计频率。它可以自动对键进行计数，支持常数时间的更新和查找操作。以下是一个示例：

  from collections import Counter
  
  my_list = ['apple', 'banana', 'apple', 'orange', 'banana', 'banana']
  my_counter = Counter(my_list)
  print(my_counter)  # 输出 Counter({'banana': 3, 'apple': 2, 'orange': 1})
  

• hashlib：Python 内置的哈希库，提供了多种哈希算法的实现，比如 MD5、SHA1、SHA256 等。可以用于对字符串、文件等进行哈希计算。以下是一个示例：

  import hashlib
  
  my_str = 'hello, world!'
  my_hash = hashlib.md5(my_str.encode()).hexdigest()
  print(my_hash)  # 输出 3e25960a79dbc69b674cd4ec67a72c62
  

除了这些库之外，Python 还有许多其他的哈希表实现库，比如 Redis、Memcached 等，它们可以用于分布式缓存、数据存储等场景。

除了自带的哈希表，python还有另一个黑科技，zip()：

zip() 函数是 Python 内置的一个函数，它可以将多个可迭代对象打包成一个元组序列，然后返回这个序列。打包后的序列的长度由最短的可迭代对象决定。

zip() 函数的语法如下：

pythonCopy code
zip(iterable1, iterable2, iterable3, ...)

其中，iterable1、iterable2、iterable3 等都是可迭代对象，可以是列表、元组、字典、集合等。

下面是一个简单的示例，演示了如何使用 zip() 函数打包两个列表：

pythonCopy code
a = [1, 2, 3]
b = [4, 5, 6]
result = zip(a, b)
print(list(result))  # 输出 [(1, 4), (2, 5), (3, 6)]

在这个例子中，我们将两个列表 a 和 b 打包成了一个元组序列，然后将序列转换为列表并输出。

如果要解包打包后的元组序列，可以使用 zip() 函数的反函数 zip(*)，如下所示：

pythonCopy code
a = [1, 2, 3]
b = [4, 5, 6]
zipped = zip(a, b)
unzipped = zip(*zipped)
print(list(unzipped))  # 输出 [(1, 2, 3), (4, 5, 6)]

在这个例子中，我们将两个列表 a 和 b 打包成了一个元组序列，然后使用 zip(*zipped) 反函数将其解包。反函数 zip(*) 的作用是将多个可迭代对象解包成多个元组，然后将这些元组打包成一个元组序列返回。这个例子中，我们使用了两次 zip() 函数，第一次是打包，第二次是解包，结果是原来的两个列表重新组合成了一个元组序列。

好了，python写就是调库，剩下的你只需要判断出这个题用的是哈希表就行了。如果你不嫌长，很多题目都可以直接一行代码AC😄。

383. 赎金信 - 力扣（Leetcode）

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入： ransomNote = "a", magazine = "b" 输出： false

示例 2：

输入： ransomNote = "aa", magazine = "ab" 输出： false

示例 3：

输入： ransomNote = "aa", magazine = "aab" 输出： true

 

提示：

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote 和 magazine 由小写英文字母组成

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        r = Counter(ransomNote)
        m = Counter(magazine)
        return not r-m

代码中用到了 Python 的 Counter 类，它可以用来统计可迭代对象中各个元素的数量，返回一个字典，其中键为元素，值为元素的数量。例如，Counter('hello') 返回的是 {'h': 1, 'e': 1, 'l': 2, 'o': 1}。

具体来说，代码中首先通过 Counter 函数分别统计了字符串 ransomNote 和 magazine 中各个字符的数量，得到两个字典 r 和 m。然后使用集合运算符 - 来计算 r 减去 m，如果结果是一个空字典，说明 magazine 中的字符可以组成 ransomNote，返回 True；否则返回 False。

值得注意的是，集合运算符 - 在这里的作用是计算两个字典的差集，返回的是包含所有在 r 中但不在 m 中的键值对的字典。因此，如果 r-m 返回的是一个空字典，说明 r 中的所有键值对都在 m 中出现过，即 magazine 中的字符可以组成 ransomNote。

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        return not Counter(ransomNote)-Counter(magazine)

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

这题和上一题异曲同工，不多做解释。

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

205. 同构字符串 - 力扣（Leetcode）

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

  示例 1:

输入： s = "egg", t = "add" 输出： true

示例 2：

输入： s = "foo", t = "bar" 输出： false

示例 3：

输入： s = "paper", t = "title" 输出： true

 

提示：

• 1 <= s.length <= 5 * 104
• t.length == s.length
• s 和 t 由任意有效的 ASCII 字符组成

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s2t, t2s = {}, {}
        for a, b in zip(s, t):
            # 对于已有映射 a -> s2t[a]，若和当前字符映射 a -> b 不匹配，
            # 说明有一对多的映射关系，则返回 false ；
            # 对于映射 b -> a 也同理
            if a in s2t and s2t[a] != b or b in t2s and t2s[b] != a:
                return False
            s2t[a], t2s[b] = b, a
        return True 

这里是用两个字典实现双向绑定，该算法的时间复杂度为 O(n)，其中 n 表示字符串 s 和 t 的长度。具体来说，需要遍历两个字符串并建立映射关系，每个字符最多只会遍历一次。同时，由于使用了两个哈希表，空间复杂度也为 O(n)。

算法的实现思路如下：

1. 首先创建两个空的字典 s2t 和 t2s，分别用于记录 s 中的字符到 t 中字符的映射关系和 t 中的字符到 s 中字符的映射关系；

2. 然后使用 zip 函数将字符串 s 和 t 中的字符一一打包，然后在循环中访问每个元组中的元素；

3. 对于每个字符，我们首先判断它是否已经在 s2t 中出现过，并且 s2t[x] 是否等于 y，或者是否已经在 t2s 中出现过，并且 t2s[y] 是否等于 x。如果满足这些条件，则说明两个字符串不同构，我们直接返回 False；

4. 否则，我们就在 s2t 和 t2s 中分别添加新的映射关系；

5. 最后，如果循环结束，仍然没有返回 False，则说明两个字符串同构，我们返回 True。

290. 单词规律 - 力扣（Leetcode）

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s ****中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = "abba", s = "dog cat cat dog" 输出: true

示例 2:

输入: pattern = "abba", s = "dog cat cat fish" 输出: false

示例 3:

输入: pattern = "aaaa", s = "dog cat cat dog" 输出: false

 

提示:

• 1 <= pattern.length <= 300
• pattern 只包含小写英文字母
• 1 <= s.length <= 3000
• s 只包含小写英文字母和 ' '
• s 不包含 任何前导或尾随对空格
• s 中每个单词都被 单个空格 分隔

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        s = s.split(' ')
        if len(s) != len(pattern):
            return False
        
        mapping = list(set([*zip(pattern, s)]))

        for i in range(len(mapping)):
            for j in range(i+1, len(mapping)):
                if mapping[i][0] == mapping[j][0] or mapping[i][1] == mapping[j][1]:
                    return False
        return True

这段代码是用来判断一个字符串 s 是否符合给定的字符串模式 pattern 的。函数名为 wordPattern，它接收两个参数 pattern 和 s，都是字符串类型的，分别表示模式和待匹配的字符串。函数返回一个布尔值，如果 s 符合模式 pattern，则返回 True，否则返回 False。

在函数中，首先使用字符串的 split() 方法将字符串 s 拆分成一个单词列表，存储在变量 s 中。然后，判断单词列表的长度是否与模式串的长度相同，如果不同，则直接返回 False。

接下来，我们需要构建一个映射表 mapping，用于记录模式串中每个字符与对应单词之间的映射关系。由于一个字符可能对应多个不同的单词，因此我们使用列表 mapping 来存储所有可能的映射关系。为了避免重复的映射关系，我们先将 pattern 和 s 中的字符和单词进行一一配对，然后使用 set 去重，最终得到一个不重复的映射关系列表 mapping。

最后，我们需要检查 mapping 中的映射关系是否满足要求，即每个字符和单词之间都是一一对应的。我们可以使用两层循环来遍历 mapping 列表中的所有映射关系，对于任意两个映射关系 (c1, w1) 和 (c2, w2)，如果两个字符或两个单词相同，则说明不符合要求，直接返回 False。否则，继续检查下一对映射关系。

如果循环中没有返回 False，则说明所有的映射关系都符合要求，函数返回 True。

这里是用了一个散列表，该算法的时间复杂度是 O(n2)O(n^2)O(n2)，其中 n 表示模式串 pattern 和待匹配的字符串 s 的长度。

当然也可以改成和上一题一样的写法

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        s = s.split(' ')
        if len(s) != len(pattern):
            return False
        
        p2s,s2p={},{}
        for x,y in zip(pattern,s):
            if x in p2s and p2s[x] != y or y in s2p and s2p[y] != x:
                return False
            p2s[x] = y
            s2p[y] = x
        return True

该算法的时间复杂度为 O(n)，其中 n 表示字符串 s 的长度。具体来说，需要将字符串 s 拆分成单词，然后遍历单词和模式串中的字符并建立映射关系，每个单词和字符最多只会遍历一次。同时，由于使用了两个哈希表，空间复杂度也为 O(n)。

这里多了一个判断s和pattern长度是否相等的代码，因为存在这样样例：

49. 字母异位词分组 - 力扣（Leetcode）

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

输入: strs = [""] 输出: [[""]]

示例 3:

输入: strs = ["a"] 输出: [["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写字母

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mapping = defaultdict(list)

        for s in strs:
            key = "".join(sorted(s))
            mapping[key].append(s)

        print(mapping)

        return mapping.values()

算法通过使用Python内置的defaultdict数据结构创建一个名为mapping的字典。对于每个输入字符串s，算法通过将其字母按照升序排序来创建一个唯一的键key。然后，将原始字符串s添加到具有相同键的列表中。最后，将字典中的值转换为列表并返回。

时间复杂度：假设有N个输入字符串，每个字符串的长度为K，排序一个长度为K的字符串需要O(KlogK)的时间。因此，总时间复杂度为O(NKlogK)。

空间复杂度：算法使用了一个defaultdict来存储输入字符串，该数据结构需要O(NK)的空间，用于存储所有的输入字符串和对应的键。

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

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

 

示例 1：

输入： nums = [2,7,11,15], target = 9 输出： [0,1] 解释： 因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入： nums = [3,2,4], target = 6 输出： [1,2]

示例 3：

输入： nums = [3,3], target = 6 输出： [0,1]

 

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

 

进阶： 你可以想出一个时间复杂度小于 O(n2) 的算法吗？

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = defaultdict()

        for i,n in enumerate(nums):
            if target - n in d.keys():
                return [d[target-n],i]
            d[n] = i
        return [-1,-1]    

该方法使用了 Python 内置的 defaultdict 数据结构来记录 nums 中每个数字的索引。然后，它遍历输入列表 nums 中的每个数字，并检查 target - n 是否已经在 defaultdict 中。如果 target - n 存在于 defaultdict 中，则返回包含对应索引的列表。否则，将数字 n 和它的索引 i 存储到 defaultdict 中，以备后续使用。

如果在遍历完整个 nums 后都没有找到符合条件的两个数字，该方法将返回 [-1, -1]。

该算法的时间复杂度为 O(n)，其中 n 是输入列表 nums 的长度。该算法遍历了一次输入列表，每次循环的时间复杂度为 O(1)，因为 defaultdict 中的查找和插入操作的时间复杂度均为 O(1)。

空间复杂度为 O(n)，因为最坏情况下，defaultdict 中需要存储输入列表 nums 中的每个数字及其索引，即需要 O(n) 的空间。

        # 借助Python特性硬着头皮判断
        # 时间复杂度O(n^2)，空间复杂度O(1)
        for i in range(len(nums)):
            if target - nums[i] in nums:      
            # 看看相减之后是不是也在列表中
                if i != nums.index(target - nums[i]):   
                # 排除重复使用同一个数的情况
                    return [i,nums.index(target - nums[i])]
        return [-1,-1]

这样写和暴力法没区别啊， 该算法使用了两重循环。外层循环 for i in range(len(nums)) 遍历列表中的每个数字，内层循环 if target - nums[i] in nums: 检查是否存在另一个数字与当前数字相加等于目标值 target，并且 if i != nums.index(target - nums[i]) 检查该数字不是当前数字本身。因为内层循环中使用了 in 和 .index() 方法来查找数字，这样做的时间复杂度为 O(n)，因此总时间复杂度为 O(n2)O(n^2)O(n2)。

219. 存在重复元素 II - 力扣（Leetcode）

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 **i 和 **j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

 

示例 1：

输入： nums = [1,2,3,1], k = 3 输出： true

示例 2：

输入： nums = [1,0,1,1], k = 1 输出： true

示例 3：

输入： nums = [1,2,3,1,2,3], k = 2 输出： false

提示：

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        d = dict.fromkeys(nums)
        for i,n in enumerate(nums):
            if d[n] != None and i - d[n] <= k:
                return True
            d[n] = i
        return False

算法思路：

1. 创建一个字典 d，将 nums 数组中的元素作为键，初始值都为 None。

2. 遍历 nums 数组，对于每个元素 n，如果 d[n] 不为 None 且 i - d[n] <= k，则返回 True。

3. 更新 d[n] 为当前下标 i。

4. 如果整个数组遍历结束后都没有返回 True，则返回 False。

时间复杂度：O(n)O(n)O(n)，其中 n 是数组 nums 的长度。

空间复杂度：O(n)O(n)O(n)，其中 n 是数组 nums 的长度，最坏情况下所有元素都需要存入字典 d 中。

128. 最长连续序列 - 力扣（Leetcode）

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n)的算法解决此问题。

  示例 1：

输入： nums = [100,4,200,1,3,2] 输出： 4 解释： 最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：

输入： nums = [0,3,7,2,5,8,4,6,0,1] 输出： 9

 

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        maxLen = 0
        nums = set(nums)
        for n in nums:
            if n-1 not in nums:
                cur = n
                length = 1
                while cur+1 in nums:
                    cur += 1
                    length += 1
                maxLen = max(maxLen,length)
        return maxLen

这段代码实现了在给定列表 nums 中查找最长的连续子序列的长度。算法的基本思想是利用集合 (set) 的快速查找特性，逐个遍历 nums 中的每个数字，检查它是否是一个序列的起点，如果是，则向后搜索该序列，直到找到序列的末尾。在这个过程中，记录序列的长度并更新最长的长度值。最终返回最长的连续序列的长度。

具体来说，该算法分为以下步骤：

1. 初始化最长连续序列长度为 0，并将 nums 转换为集合，以便快速查找数字是否在 nums 中出现过。

2. 对 nums 中的每个数字 n 进行循环遍历，判断 n 是否是某个连续序列的起点。

   • 如果 n-1 不在 nums 集合中，说明 n 是一个新序列的起点，此时需要在集合中向后查找，找到该序列的末尾，统计序列的长度，并更新最长连续序列长度。
   • 如果 n-1 在 nums 集合中，说明 n 不是一个新序列的起点，可以直接跳过该数字继续循环遍历 nums。

3. 返回最长连续序列的长度。

这个算法的时间复杂度为 O(n)，其中 n 是输入列表中数字的数量。因为该算法在遍历集合中每个数字时，最多需要向后搜索整个连续子序列，而且每个数字只会被遍历一次，因此算法的时间复杂度是线性的。

---