迎风起降的小站
哈希算法
蜂窝煤 Lv3
  2026-08-26 10:55:53   2026-09-22 14:53:05    

本文整理常见的哈希表题目，按题目编号记录题意、示例、限制条件和解答代码。

相关 Python 知识点

  • 列表 list []

    • 和 C 语言里的数组类似，支持动态扩容，可修改元素，有序的，可重复。
    • 添加元素使用 list.append(value)
    • 删除元素使用 list.remove(value) 或 del list[index]。
    • 可作栈使用，使用 list.append(value) 入栈，list.pop() 出栈。
    • 访问方式为 list[index]，索引从 0 开始。
    • in 操作可用于判断元素是否在列表中，时间复杂度为 $O(n)$。
    • 切片操作 list[start:end]，返回从 start 到 end-1 的子列表。
      • list[:end]，返回从索引 0 到 end-1 的子列表。
      • list[start:]，返回从索引 start 到列表末尾的子列表。
      • list[:]，返回整个列表的副本。

  • 集合 set {}

    • 和数学中的集合类似，元素唯一，无序的。
    • 添加元素使用 set.add(value)。
    • 删除元素使用 set.remove(value) 或 set.discard(value)。
    • 访问方式为 value in set，判断元素是否在集合中，平均时间复杂度为 $O(1)$。

  • 字典 dict {}

    • 添加或修改元素使用 dict[key] = value。
    • 删除元素使用 del dict[key]。
    • 访问方式为 dict[key]，获取键对应的值，平均时间复杂度为 $O(1)$。

  • 元组 tuple ()

    • 和列表类似，但不可修改元素，有序的，可重复。
    • 访问方式为 tuple[index]，索引从 0 开始。
    • in 操作可用于判断元素是否在元组中，时间复杂度为 $O(n)$。
    • 元组可作为字典的键或集合的元素，而列表不可。

题目索引

题号 题目 难度
1 两数之和 简单
49 字母异位词分组 中等
128 最长连续序列 中等
349 两个数组的交集 简单
202 快乐数 简单
15 三数之和 中等
383 赎金信 简单
454 四数相加 II 中等

两数之和

题号：1
难度：简单

题目描述

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

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

示例

示例 1：

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

示例 2：

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

示例 3：

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

提示

  • 2 <= nums.length <= 10^4
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9
  • 只会存在一个有效答案

解答

思路

最直接的做法是使用两个 for 循环进行暴力枚举。

为了降低时间复杂度，可以将“寻找两个数的和”转换为“寻找当前数字的补数”。对于当前数字 num，需要查找的补数为 target - num。

遍历数组时，使用字典记录已经遍历过的数字及其下标，就可以在平均 $O(1)$ 的时间内判断补数是否存在。

暴力解法 $O(n^2)$

1
2
3
4
5
6
7
8
9
from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i, num_i in enumerate(nums):
            for j, num_j in enumerate(nums[i + 1:], start=i + 1):
                if num_i + num_j == target:
                    return [i, j]

时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$。

哈希表解法 $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
from collections import defaultdict
from typing import List


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

        for i, num in enumerate(nums):
            complement = target - num
            if complement in seen:
                return [seen[complement], i]
            seen[num] = i

时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

字母异位词分组

题号：49
难度：中等

题目描述

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

示例

示例 1：

1
2
输入：strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出：[["bat"],["nat","tan"],["ate","eat","tea"]]

解释：

  • 在 strs 中没有字符串可以通过重新排列来形成 “bat”。
  • 字符串 “nat” 和 “tan” 是字母异位词，因为它们可以重新排列以形成彼此。
  • 字符串 “ate”、”eat” 和 “tea” 是字母异位词，因为它们可以重新排列以形成彼此。

示例 2：

1
2
输入：strs = [""]
输出：[[""]]

示例 3：

1
2
输入：strs = ["a"]
输出：[["a"]]

提示

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

解答

思路

暴力解法就是将 n 个字符串进行排序，排序后等价的异位词会得到相同的排序结果（key），然后将相同的排序结果归为一组（value）。

因为暴力解法的排序带来了 k log k 的复杂度，可以想办法优化构造 key 的过程。我们可以利用统计的做法，构造一个长度为 26 的特征数组，每一位代表一个字母，用这个数组作为 key，这样对于每个字符串只需要 k 的时间复杂度即可。

暴力解法 $O(n k \log k)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from collections import defaultdict
from typing import List


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

        for s in strs:
            group[''.join(sorted(s))].append(s)

        for k in group:
            result.append(group[k])

        return result

最优解 $O(n k)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import defaultdict
from typing import List


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

        for s in strs:
            key = [0] * 26

            for c in s:
                key[ord(c) - ord('a')] += 1

            group[tuple(key)].append(s)

        for k in group:
            result.append(group[k])

        return result

最长连续序列

题号：128
难度：中等

题目描述

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

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

示例

示例 1：

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

示例 2：

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

示例 3：

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

提示

  • 0 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9

解答

思路

暴力解法很简单，给定的数组没有排序，先排序后进行一次遍历即可，也就是 n log n + n 的时间复杂度。

最优解法是，找一个连续的序列首先得找到一个起点，然后从这个起点开始以 1 步进查找序列下一个数字是否在数组里。不断查找这一步要用 dict 来进行优化，最后就能得到一个 $O(n)$ 的时间复杂度。

暴力解法 $O(n \log n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from typing import List


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # 避免数组越界
        if not nums:
            return 0
        sort_nums = sorted(nums)
        cur_num = sort_nums[0]
        max_len = 1
        cur_len = 1
        for num in sort_nums[1:]:
            # 重复数字跳过
            if num == cur_num:
                continue
            # 序列中断，重置长度计数器
            elif num != cur_num + 1:
                cur_len = 1
            # 序列连续
            else:
                cur_len += 1
            cur_num = num
            max_len = max(max_len, cur_len)
        return max_len

最优解法 $O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from typing import List


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        max_len = 0
        nums_set = set(nums)
        for num in nums_set:
            # 判断起点
            if num - 1 not in nums_set:
                # 是起点，沿着起点走一下
                cur_num = num
                cur_len = 1
                while cur_num + 1 in nums_set:
                    cur_len += 1
                    cur_num += 1
                max_len = max(max_len, cur_len)
        return max_len

两个数组的交集

题号：349
难度：简单

题目描述

给定两个数组 nums1 和 nums2，返回 它们的交集。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序。

示例

示例 1：

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

1
2
3
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的。

提示

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

解答

思路

先分别使用 set 对两个数组去重，然后遍历 nums1_set，检查当前元素是否存在于 nums2_set 中。

判断元素是否存在时使用集合的 in 操作，平均时间复杂度为 $O(1)$；如果直接在列表中查找，时间复杂度会增加到 $O(n)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from typing import List


class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1_set = set(nums1)
        nums2_set = set(nums2)
        result = []

        for num in nums1_set:
            if num in nums2_set:
                result.append(num)

        return result

快乐数

题号：202
难度：简单

题目描述

编写一个算法来判断一个数 n 是不是快乐数。

“快乐数” 定义如下：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能会无限循环但始终变不到 1。
  • 如果这个过程的结果为 1，那么这个数就是快乐数。
  • 如果 n 是快乐数就返回 true，否则返回 false。

示例

示例 1：

1
2
3
4
5
6
7
输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

示例 2：

1
2
输入：n = 2
输出：false

提示

  • 1 <= n <= 2^31 - 1

解答

这个题其实不难，主要是要知道如果不是快乐数，一定会进入循环。所以我们用一个集合set保存出现过的数字，如果出现过的数再次出现，就说明进入循环了，返回False。

那么为啥一定会循环呢，因为每一位数字的取值是0到9，平方后每一位的取值是0到81，假设n有k位，那么平方和的最大值就是k81。对于一个k位数，k81的最大值是9*81=729，所以平方和的结果一定会小于等于729；而且平方和的结果是整数，取值范围有限，所以如果不是快乐数，一定会进入循环。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from typing import List
class Solution:
    def isHappy(self, n: int) -> bool:
        state = set()
        cur_n = n
        while cur_n not in state:
            next_n = 0
            for c in str(cur_n):
                next_n += int(c) ** 2
            if next_n == 1:
                return True
            state.add(cur_n)
            cur_n = next_n
        return False

三数之和

题号：15
难度：中等

题目描述

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且 不重复 的三元组。

注意： 答案中不可以包含重复的三元组。

示例

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0
不同的三元组是 [-1,0,1] 和 [-1,-1,2]。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

1
2
3
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0。

示例 3：

1
2
3
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0。

提示

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

解答

思路

三数之和可以拆解为两数之和：先固定一个数 nums[i]，然后在后面的元素中寻找两个数，使它们的和等于 -nums[i]。

对于固定的 nums[i]，使用集合 seen 保存已经遍历过的数字。遍历当前数字 nums[j] 时，只需要判断它的补数 -nums[i] - nums[j] 是否存在于 seen 中。

本题要求的是不重复的数值三元组，而不是所有合法的下标组合。因此，将找到的三元组排序后转为元组，并存入集合 results，即可自动去重。

哈希表解法 $O(n^2)$

这份哈希表解法的时间复杂度为 $O(n^2)$，但在 LeetCode 上可能超时。这道题通常使用排序加双指针的方法进一步优化。

排序加左右指针的优化版本请参考：双指针：三数之和。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        results = set()
        for i in range(len(nums)):
            seen = set()
            for j in range(i + 1, len(nums)):
                need = -nums[i] - nums[j]
                if need in seen:
                    results.add(tuple(sorted([nums[i], nums[j], need])))
                seen.add(nums[j])
        return [list(t) for t in results]

赎金信

题号：383
难度：简单

题目描述

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

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

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

示例

示例 1：

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

示例 2：

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

示例 3：

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

提示

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

解答

思路

有点像同字母异位词的做法，只要统计 magazine 中每个字母的数量，然后遍历 ransomNote，每遇到一个字母就将对应的数量减一，如果减到小于零，就说明 magazine 中没有足够的该字母，返回 False。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        m_chars = [0] * 26
        for m in magazine:
            m_chars[ord(m)-ord('a')] += 1
        for r in ransomNote:
            m_chars[ord(r)-ord('a')] -= 1
            if m_chars[ord(r)-ord('a')] < 0:
                return False
        return True

四数相加 II

题号：454
难度：中等

题目描述

给你四个整数数组 nums1、nums2、nums3 和 nums4，数组长度都是 n，请你计算有多少个元组 (i, j, k, l) 能满足：

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例

示例 1：

1
2
3
4
5
6
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

1
2
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

提示

  • n == nums1.length
  • n == nums2.length
  • n == nums3.length
  • n == nums4.length
  • 1 <= n <= 200
  • -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

解答

思路

将四个数组分成两组，组合成左边数字和右边数字，然后用两数之和的思路做就好了

1
2
3
4
5
6
7
8
9
10
11
from collections import defaultdict
class Solution:
    def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
        l_sums = defaultdict(int)
        r_sums = defaultdict(int)
        nums_len = len(nums1)
        for i in range(nums_len):
            for j in range(nums_len):
                l_sums[nums1[i]+nums2[j]] += 1
                r_sums[nums3[i]+nums4[j]] += 1
        return sum(l_sums[l] * r_sums.get(-l, 0) for l in l_sums)
 评论
评论插件加载失败
正在加载评论插件
  1. 1. 相关 Python 知识点
  2. 2. 题目索引
  3. 3. 两数之和
    1. 3.1. 题目描述
    2. 3.2. 示例
    3. 3.3. 提示
    4. 3.4. 解答
      1. 3.4.1. 思路
      2. 3.4.2. 暴力解法 $O(n^2)$
      3. 3.4.3. 哈希表解法 $O(n)$
  4. 4. 字母异位词分组
    1. 4.1. 题目描述
    2. 4.2. 示例
    3. 4.3. 提示
    4. 4.4. 解答
      1. 4.4.1. 思路
      2. 4.4.2. 暴力解法 $O(n k \log k)$
      3. 4.4.3. 最优解 $O(n k)$
  5. 5. 最长连续序列
    1. 5.1. 题目描述
    2. 5.2. 示例
    3. 5.3. 提示
    4. 5.4. 解答
      1. 5.4.1. 思路
      2. 5.4.2. 暴力解法 $O(n \log n)$
      3. 5.4.3. 最优解法 $O(n)$
  6. 6. 两个数组的交集
    1. 6.1. 题目描述
    2. 6.2. 示例
    3. 6.3. 提示
    4. 6.4. 解答
      1. 6.4.1. 思路
  7. 7. 快乐数
    1. 7.1. 题目描述
    2. 7.2. 示例
    3. 7.3. 提示
    4. 7.4. 解答
  8. 8. 三数之和
    1. 8.1. 题目描述
    2. 8.2. 示例
    3. 8.3. 提示
    4. 8.4. 解答
      1. 8.4.1. 思路
      2. 8.4.2. 哈希表解法 $O(n^2)$
  9. 9. 赎金信
    1. 9.1. 题目描述
    2. 9.2. 示例
    3. 9.3. 提示
    4. 9.4. 解答
      1. 9.4.1. 思路
  10. 10. 四数相加 II
    1. 10.1. 题目描述
    2. 10.2. 示例
    3. 10.3. 提示
    4. 10.4. 解答
      1. 10.4.1. 思路
  1. 1. 相关 Python 知识点
  2. 2. 题目索引
  3. 3. 两数之和
    1. 3.1. 题目描述
    2. 3.2. 示例
    3. 3.3. 提示
    4. 3.4. 解答
      1. 3.4.1. 思路
      2. 3.4.2. 暴力解法 $O(n^2)$
      3. 3.4.3. 哈希表解法 $O(n)$
  4. 4. 字母异位词分组
    1. 4.1. 题目描述
    2. 4.2. 示例
    3. 4.3. 提示
    4. 4.4. 解答
      1. 4.4.1. 思路
      2. 4.4.2. 暴力解法 $O(n k \log k)$
      3. 4.4.3. 最优解 $O(n k)$
  5. 5. 最长连续序列
    1. 5.1. 题目描述
    2. 5.2. 示例
    3. 5.3. 提示
    4. 5.4. 解答
      1. 5.4.1. 思路
      2. 5.4.2. 暴力解法 $O(n \log n)$
      3. 5.4.3. 最优解法 $O(n)$
  6. 6. 两个数组的交集
    1. 6.1. 题目描述
    2. 6.2. 示例
    3. 6.3. 提示
    4. 6.4. 解答
      1. 6.4.1. 思路
  7. 7. 快乐数
    1. 7.1. 题目描述
    2. 7.2. 示例
    3. 7.3. 提示
    4. 7.4. 解答
  8. 8. 三数之和
    1. 8.1. 题目描述
    2. 8.2. 示例
    3. 8.3. 提示
    4. 8.4. 解答
      1. 8.4.1. 思路
      2. 8.4.2. 哈希表解法 $O(n^2)$
  9. 9. 赎金信
    1. 9.1. 题目描述
    2. 9.2. 示例
    3. 9.3. 提示
    4. 9.4. 解答
      1. 9.4.1. 思路
  10. 10. 四数相加 II
    1. 10.1. 题目描述
    2. 10.2. 示例
    3. 10.3. 提示
    4. 10.4. 解答
      1. 10.4.1. 思路