LeetCode 1. 两数之和

本节目标

从平方级枚举推导出一次遍历的哈希补数查询，并理解先查后存的不变量。

这道题是哈希表解题框架的第一道母题。重点不在记住几行代码，而在于识别“为当前元素寻找一个历史配对元素”的问题模型。

查看原题

题意与约束

给定整数数组 nums 和整数目标值 target，找出两个不同位置，使这两个位置上的数之和等于 target，并返回它们的下标。

题目保证恰好有一个有效答案，同一个位置不能重复使用，返回两个下标的先后顺序不限。因为要返回原数组下标，任何会改变元素位置的处理都必须额外保存下标关系。

从暴力搜索到补数查询

最直接的办法是枚举两个下标：固定 i，再枚举所有 j > i，检查 nums[i] + nums[j] == target。它容易写对，但最坏要检查约 n(n - 1) / 2 对元素，时间复杂度为 O(n²)。

瓶颈不是加法，而是：对每个 nums[i]，我们都重新扫描其余元素，寻找值为 target - nums[i] 的数。

把问题改写一下：遍历到值 x 时，如果此前已经出现过补数 target - x，答案就已经确定。于是我们用映射 seen 保存：

已经出现的数值 -> 该数值对应的下标

对每个位置只做一次补数查询和一次写入，就能去掉内层循环。

以 nums = [2, 7, 11, 15]、target = 9 为例：

当前下标	当前值	要找的补数	查询前 `seen`	操作
0	2	7	`{}`	未命中，记录 `2 -> 0`
1	7	2	`{2: 0}`	命中下标 0，返回 `[0, 1]`

为什么必须先查后存

进入第 i 轮时，我们维持这个循环不变量：seen 只保存下标小于 i 的元素。因此，一旦补数命中，取出的下标 j 一定满足 j < i，两个位置自然不同。

若先存当前值再查询，假设当前值恰好等于自己的补数，程序就可能用同一个位置配对自己。例如 target = 6、当前值为 3 时，刚写入的 3 会立刻被查到。

正确的先查后存也不会漏掉两个相同数值。对 nums = [3, 3]、target = 6：

第一个 3 查询失败后记录下标 0；
第二个 3 查询时命中下标 0，返回 [0, 1]。

所以操作顺序不是代码风格，而是“不重复使用同一位置”这一约束在算法中的直接表达。

代码实现

两份源码使用同一算法和同一不变量：映射只保存已经遍历过的值与下标，当前轮先查询补数，再记录当前值。页面展示的就是自动测试实际编译、执行的文件。

C++
Python

C++17
#include <unordered_map>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> seen;
        for (int idx = 0; idx < static_cast<int>(nums.size()); ++idx) {
            int val = nums[idx];
            int need = target - val;
            // 查询历史补数
            auto it = seen.find(need);
            if (it != seen.end()) {
                return {it->second, idx};
            }
            // 记录当前数
            seen[val] = idx;
        }
        return {};
    }
};

Python 3
class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        seen: dict[int, int] = {}
        for idx, val in enumerate(nums):
            need = target - val
            # 查询历史补数
            if need in seen:
                return [seen[need], idx]
            # 记录当前数
            seen[val] = idx
        return []

C++ 使用 unordered_map<int, int>，并用 find 区分“键不存在”和“键对应下标为 0”。Python 使用字典并通过 need in seen 判断存在性；其中 idx 是当前下标，val 是当前值，need 是要查询的补数。题目保证有解，因此正常评测会在循环中返回；末尾的空数组用于保持函数在所有路径上都有返回值。

复杂度分析

时间复杂度：期望 O(n)。数组只遍历一次，每轮进行均摊常数时间的哈希查询和插入；极端哈希冲突下可能退化。
空间复杂度：O(n)。最坏情况下，找到答案前需要记录线性数量的元素。

与暴力算法相比，我们用额外的线性空间消除了重复的线性查询。

易错点

先存后查：可能让当前元素匹配自身，尤其容易在 target = 2 * nums[i] 时出错。
只保存值，不保存下标：题目要求返回位置，因此需要映射而不是仅用集合。
用映射取值代替存在性判断：有效答案可能包含下标 0，不能把值 0 当成“不存在”。
排序后直接返回位置：排序能配合双指针找数值，但会打乱原下标；本题用哈希表更直接。
覆盖重复值后担心丢解：在题目保证唯一答案的前提下，先查后存仍能正确处理重复值；命中时返回任一已保存的合法历史下标即可。

模式迁移

记住的不是“看到两数之和就用哈希表”，而是下面这个可迁移的判断链：

暴力过程是否在反复寻找某个目标信息？
这个目标能否由当前元素直接推导？
是否只需在已经处理过的元素中查询？
查询命中后，需要从哈希表取回存在性、次数、下标，还是一组元素？

沿着这条链可以继续练习：

字母异位词分组：把“补数”换成字符串的规范化特征，映射值从下标变成分组列表。
最长连续序列：只查询相邻数字是否存在，因此由映射退化为集合，并通过只从起点扩展避免重复扫描。
前缀和计数类问题：把“当前数的补数”换成“当前前缀所需的历史前缀”，映射中保存出现次数。

这三类题分别对应哈希表的三个核心用途：恢复关联信息、判断存在性、统计历史状态。

本节目标

题意与约束​

从暴力搜索到补数查询​

为什么必须先查后存​

代码实现​

复杂度分析​

易错点​

模式迁移​