两数之和：从暴力到哈希

1.2 两数之和：从暴力到哈希

本节摘要：两数之和是全册进化链的第一次完整演示。我们从嵌套循环的平方级暴力解出发，定位"回头查找配对"这个瓶颈，用哈希表把查找降为常数时间，一次性完成从 O(n 的平方) 到 O(n) 的跃迁，并给出 Java 与 Python 双实现、边界清单与三数之和的延伸方向。

从一道人人熟知的题说起

上一节建好了复杂度这把尺子，本节马上把它用起来——承接下来的度量衡，通往第二章的分治与哈希思想。题目本身几乎不用介绍：给定整数数组 nums 与整数 target，数组中恰好存在两个数之和等于 target，返回它们的下标。样例输入 nums 等于 2、7、11、15，target 等于 9，输出下标 0 与 1，因为 2 加 7 等于 9。假设每种输入恰好有唯一解，同一元素不能重复使用。

一、暴力解：正确但昂贵

最直接的写法不需要任何灵感：把所有数对都试一遍。外层固定第一个数，内层从它的下一个位置开始找第二个数，逐对求和，命中即返回。

def two_sum_brute(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

nums = [2, 7, 11, 15]
print(two_sum_brute(nums, 9))   # 输出 [0, 1]
​

时间复杂度：外层 n 次，内层平均二分之 n 次，合计约 n 的平方的一半，记 O(n 的平方)。空间复杂度 O(1)。拿上一节的口诀验算：n 等于一千时约五十万次操作，瞬间完成；n 等于一万时约五千万次，零点几秒，还能过；n 等于十万时约五十亿次，几十秒起步，超时铁板钉钉。暴力解的正确性无可挑剔，它的全部问题只有一个字：慢。

二、找瓶颈：重复的不是计算，是查找

按进化流程追问：开销最高的操作是什么？不是加法——加法是 O(1)，便宜得很；是内层那个"扫描"，我在外层确定了 nums[i] 之后，需要问数组一个问题：target 减 nums[i] 这个值，你里面有吗？数组用一次完整扫描来回答，每次回答都花 O(n)。同样的查找问题被问了 n 遍，这就是平方的来源。

瓶颈既然在"查找"，就问下一个问题：有没有查找更快的等价数据结构？有——哈希表。它用空间换时间，把"这个值存在吗、存在哪个下标"降到平均 O(1)。于是进化版呼之欲出：遍历数组，每遇到一个数，先查哈希表里有没有它的"另一半"，有则直接返回；没有则把自己存进表，继续走。

def two_sum(nums, target):
    seen = {}                     # 值到下标的映射
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:          # 查找 O(1)
            return [seen[need], i]
        seen[x] = i               # 查无此伴，先把自己登记
    return []

print(two_sum([2, 7, 11, 15], 9))    # 输出 [0, 1]
print(two_sum([3, 2, 4], 6))         # 输出 [1, 2]，注意不是 [0, 0]
print(two_sum([3, 3], 6))            # 输出 [0, 1]，重复值也能正确处理
​

三个细节值得咀嚼。第一，为什么"先查再存"而不是"先存再查"？因为先查再存天然避免自己配自己：处理下标 0 的 3 时表是空的，查不到另一半，只会等下标处的另个 3 进表后才配对成功，target 等于 6、数组为 3、3 的用例因此正确。若先存再查，第一次循环就能查到自己，返回两个相同下标，直接错。第二，哈希表的 O(1) 是平均口径，最坏情形（哈希冲突全撞一格）会退化，但面试中引用平均复杂度即可，能主动提一句退化条件是加分项。第三，空间从 O(1) 涨到 O(n)，这就是空间换时间的标价——绝大多数时候这笔交易血赚，但内存受限的嵌入式场景就得掂量。

Java 版本对照，思路完全一致：

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        if (seen.containsKey(need)) {
            return new int[]{seen.get(need), i};
        }
        seen.put(nums[i], i);
    }
    return new int[]{};
}
// 运行：twoSum(new int[]{2, 7, 11, 15}, 9) 返回 [0, 1]
​

一次遍历中哈希表与配对查找的配合

三、边界清单与变式

这道题的边界坑位不多，但每个都高频：数组只有两个元素且互为配对（上面 3、3 的用例）；解的两个数值相同但下标不同；负数参与求和（逻辑不变，但心算样例时容易乱）；题目若改成"数组有序"，那就是另一条进化链的入口——相向双指针可以在 O(n) 时间、O(1) 空间内解决，详见第二章双指针一节。

变式方面，三数之和沿用同一套思路推进一小步：先排序，外层固定一个数，内层转化为有序数组上的两数之和，用相向双指针代替哈希，整体复杂度 O(n 的平方)。四数之和则是再套一层固定。你可以看到，"两数之和"的哈希解法既是本节的落点，也是整个"求和家族"的种子——面试官最爱沿着这条种子题追问三层。

本节要点回顾

• 瓶颈定位法：先找开销最高的操作，本例中不是加法而是"存在吗"的查找；
• 先查再存的顺序是正确性关键，它防止元素和自己配对；
• 空间换时间有标价：哈希表把时间从平方压到线性，代价是 O(n) 空间；
• 哈希表的常数时间是平均口径，冲突退化情形能主动提及更稳；
• 有序变式切换武器：数组一旦有序，相向双指针以 O(1) 空间取而代之。

下一节走进链表：当数组失去随机访问能力，同样的进化逻辑会催生快慢指针这把新刀。