哈希表基础#

哈希表是一种牺牲空间换时间的数据结构，通过哈希函数将键映射到数组索引，实现快速查找。
哈希表的查询、插入和删除操作平均时间复杂度为 O(1)，在哈希冲突严重的情况下最坏可能退化为 O(n)。
常见的三种哈希结构包括：
- 数组（适用于索引范围已知的小写字母等）
- Set（无序、元素唯一）
- Map（键值对）

数组#

数组常用于当键是连续整数或字符映射为整数的情况，如 'a' - 'z' 对应 0 - 25。
数组的索引可以直接充当哈希表的键，适合小范围字符或整数的统计场景。

LeetCode 242. 有效的字母异位词#

题目链接

1
class Solution:
2
    def isAnagram(self, s: str, t: str) -> bool:
3
        # 由于字母是连续的，并且数量有限（都是小写字母），
4
        # 所以可以使用长度为26的数组来统计每个字母出现的次数
5
        # 使用 ord 将字母转换为对应的 ASCII 值，并减去 'a' 的 ASCII 值获取索引
6
        record = [0] * 26
7

8
        for ch in s:
9
            record[ord(ch) - ord('a')] += 1
10

11
        for ch in t:
12
            record[ord(ch) - ord('a')] -= 1
13

14
        # 若两个字符串是字母异位词，则每个位置上对应的计数应为 0
15
        for count in record:
16
            if count != 0:
17
                return False
18

19
        return True

Set#

Set 是一种无序且不重复的集合，适用于快速去重与查找元素是否存在。
Python 中的 set 底层是哈希表，插入、查找、删除的平均时间复杂度为 O(1)。

LeetCode 349. 两个数组的交集#

题目链接

1
class Solution:
2
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
3
        # 使用 set 来存储 nums1 中的元素
4
        # 然后判断 nums2 中哪些元素在 set1 中出现过
5
        # 将交集元素添加到结果集合 set2 中，自动去重
6
        set1 = set(nums1)
7
        result_set = set()
8

9
        for num in nums2:
10
            if num in set1:
11
                result_set.add(num)
12

13
        return list(result_set)

LeetCode 202. 快乐数#

题目链接

1
class Solution:
2
    def isHappy(self, n: int) -> bool:
3
        # 使用 set 记录出现过的数字，避免无限循环
4
        seen = set()
5

6
        while True:
7
            n = self.get_sum(n)
8
            if n == 1:
9
                return True
10
            # 若当前 n 已出现过，说明进入了循环，返回 False
11
            if n in seen:
12
                return False
13
            seen.add(n)
14

15
    def get_sum(self, n: int) -> int:
16
        # 求每个位置上的数字的平方和
17
        total = 0
18
        while n > 0:
19
            n, digit = divmod(n, 10)
20
            total += digit ** 2
21
        return total

Map#

Map 是一种键值对形式的数据结构，Python 中使用 dict 表示。
适用于快速查找、存储配对信息，如元素与索引、字符与频次等。
平均时间复杂度为 O(1)，适合大多数查找类题目。

LeetCode 1. 两数之和#

题目链接

1
class Solution:
2
    def twoSum(self, nums: List[int], target: int) -> List[int]:
3
        # 创建一个哈希表，key 为数值，value 为该数值的索引
4
        record = {}
5

6
        for i, num in enumerate(nums):
7
            complement = target - num
8
            # 若目标值已存在于哈希表中，返回其索引
9
            if complement in record:
10
                return [i, record[complement]]
11
            # 将当前数值与索引存入哈希表
12
            record[num] = i