算法刷题系列（二）：哈希表——用空间换查找

算法刷题系列（二）：哈希表——用空间换查找

本篇承接“算法刷题系列路线图”和上一篇“模拟法：从题意到状态更新”。模拟法按顺序执行每条指令；如果题目还要求反复判断某个值是否出现过，或者查询某个值对应的记录，直接扫描已有数据可能会产生大量重复工作。

哈希表可以把键映射到对应的值，让我们在通常情况下用接近 O(1) 的时间完成查找、插入和更新。本篇从一个“找出两数之和”的原创例子出发，说明怎样把查找需求变成哈希表查询，并用 Java 和 Python 实现。

一、什么时候考虑哈希表？

题目出现下面这些需求时，可以考虑哈希表：

• 判断一个值是否出现过；
• 统计每个值出现的次数；
• 根据一个键快速找到关联信息；
• 用已经访问过的元素补足当前元素所需的信息；
• 把重复扫描改成“每个元素处理一次”。

哈希表不是自动让算法变快的工具。先明确“要查什么、键是什么、值要保存什么”，再判断它是否能消除重复扫描。

二、例子：找出和为目标值的两个下标

给定整数数组 nums 和整数 target，如果存在两个不同下标 i、j 满足：

nums[i] + nums[j] = target

返回这两个下标。假设题目保证恰好存在一个答案，并且不能重复使用同一个元素。

例如：

nums   = [4, 1, 9, 6]
target = 10

答案是下标 [1, 2]，因为 nums[1] + nums[2] = 1 + 9 = 10。

三、先写出朴素做法

最直接的方法是枚举所有下标对：

for 每个 i:
    for 每个 j > i:
        检查 nums[i] + nums[j] 是否等于 target

这种方法能覆盖所有可能的答案，时间复杂度是 O(n²)，额外空间复杂度是 O(1)。

它适合作为正确性基线，但当数组变大时，会重复做很多加法和比较。固定当前数 x 之后，问题其实变成了：

之前是否见过 target - x？

这正是哈希表擅长解决的查找问题。

四、设计哈希表中保存的内容

从左到右扫描数组。处理当前下标 i 时：

1. 当前值为 x = nums[i]。
2. 需要的配对值是 target - x。
3. 在哈希表中查找这个配对值。
4. 如果找到，返回它之前保存的下标和当前下标。
5. 如果没有找到，把 x 和它的下标 i 放入哈希表。

哈希表的设计是：

部分	保存内容	原因
键（key）	已经扫描过的数值	需要按配对值快速查找
值（value）	该数值对应的一个下标	找到配对值后需要返回下标

例如扫描到 9 时，target - 9 = 1。如果哈希表中已经保存了 1 -> 1，就找到了答案 [1, 2]。

五、为什么先查找，再插入？

关键顺序是：

先查 target - 当前值
再把当前值放入哈希表

这样哈希表里只会包含当前元素之前的数，天然保证配对使用的是两个不同下标。

如果先插入再查找，还需要额外判断找到的下标是否等于当前下标。正确但多了一个容易出错的条件。

这个顺序也能正确处理重复值。例如 nums = [4, 4]、target = 8：

• 第一个 4 尚未找到配对值，于是保存 4 -> 0；
• 第二个 4 查到之前的 4 -> 0，返回 [0, 1]。

六、算法步骤与正确性

算法步骤

1. 创建空哈希表 seen。
2. 按下标从左到右遍历数组。
3. 对当前值 x，计算 need = target - x。
4. 如果 need 已在 seen 中，返回 [seen[need], i]。
5. 否则记录 seen[x] = i。

为什么不会漏掉答案？

设答案下标为 a < b。当扫描到 b 时，a 已经被处理并存入哈希表。由于：

nums[a] = target - nums[b]

查找 target - nums[b] 时会找到 a，因此算法会返回一组有效下标。

在题目保证有解的前提下，扫描过程中一定能找到答案。若题目不保证有解，函数还应定义“未找到”时的返回方式，例如返回空结果或抛出异常。

七、Java 实现

import java.util.HashMap;
import java.util.Map;

public class TwoSum {
    public static int[] findPair(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            Integer previousIndex = seen.get(need);
            if (previousIndex != null) {
                return new int[] {previousIndex, i};
            }

            seen.put(nums[i], i);
        }

        throw new IllegalArgumentException("No valid pair exists");
    }
}

这里先调用 get 再调用 put，因此不会把当前下标与自己配对。Integer 可能为 null，所以用 Integer 接收查找结果。

八、Python 实现

def find_pair(nums: list[int], target: int) -> tuple[int, int]:
    seen: dict[int, int] = {}

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

        seen[value] = i

    raise ValueError("No valid pair exists")

seen 的键是已经遍历过的数值，值是对应下标。查找成功时，返回的是两个不同位置，因为当前值是在查找失败后才加入哈希表的。

九、复杂度分析

数组中的每个元素最多执行一次哈希查找和一次插入：

• 平均时间复杂度： O(n)；
• 额外空间复杂度： O(n)。

这里的 O(n) 时间建立在哈希操作通常为平均 O(1) 的前提上。哈希冲突、具体实现和输入分布会影响实际性能，因此哈希表的“常数时间”是平均意义上的，不是对所有实现和输入的绝对保证。

和双重循环相比，这个方法用更多空间换取了更少的重复查找。

十、边界测试

配对值相同，但必须来自不同位置

nums = [4, 4], target = 8

应返回 [0, 1]，不能把同一个 4 的同一位置用两次。

包含负数

nums = [-5, 12, 3], target = 7

应返回 [-5, 12] 对应的两个下标。补数计算 target - value 对负数同样成立。

答案在数组末尾才出现

nums = [2, 5, 8, 11], target = 19

算法应在处理最后一个元素时找到前面的 8。

没有答案

示例代码在没有找到配对时会抛出异常。真实题目若规定返回特殊值，应按题目契约调整，而不是默默返回看似成功的下标。

十一、哈希表使用中的常见问题

1. 键值设计不清楚：需要快速查找的内容作为键，查到后还要使用的信息作为值。
2. 错误地先插入再查找：可能把当前元素和自身匹配。
3. 重复元素处理不当：只保存一个下标还是保存所有下标，取决于题目是否要求枚举全部答案。
4. 把平均复杂度当成绝对保证：哈希操作通常很快，但仍需结合数据结构实现理解复杂度。
5. 忽略键的相等与哈希规则：自定义对象作键时，应确保相等判断和哈希计算一致。
6. 不必要地保存整个历史：如果问题只需计数，可以存频次；如果需要恢复位置，再存下标或索引列表。

十二、从本题连接到后续主题

这道题的关键不是“记住两数之和模板”，而是把当前决策改写成对历史信息的查询：

当前元素需要什么？
        │
        ▼
target - 当前值
        │
        ▼
查找这个值是否已出现

同一思路可以迁移到频次统计、去重、分组和前缀状态查询。接下来学双指针时，可以对比另一种优化路径：哈希表通过额外空间换查找，而排序后的双指针通过利用顺序减少候选搜索。

小结

哈希表适合把“反复扫描历史记录”的问题改写成“按键查询”。解题时先确定：

1. 要查找的键是什么？
2. 找到键后还需要什么值？
3. 插入和查询的先后顺序是否影响正确性？
4. 额外空间是否符合题目约束？

本题扫描数组一次，用哈希表保存已访问值和下标，在平均 O(n) 时间内找到答案。掌握这个建模过程后，再遇到“之前是否出现过”“需要补出什么值”等信号，就可以判断哈希表是否合适。