LC1　两数之和¶

简单通过率 55.2%python3核心代码模式哈希样例通过牛客 AC数组哈希表

讲解章节：哈希表

一句话

一遍哈希，边扫边查「target 减当前值」是否已经出现过。

解题思路¶

这题考什么¶

在数组里找一对和为 target 的下标。朴素做法是双重循环枚举 (i, j)，对每个 i 都把它右边的元素扫一遍找搭档，O(n^2)。

关键观察：搭档是被唯一确定的。固定 nums[i] = x 之后，能与它配对的值只有 need = target - x 这一个。于是「在一堆数里找某个具体的值」这件事，可以用哈希表把 O(n) 的线性查找压成 O(1) 的查表。哈希表的性质见哈希表。

seen = {}                       值 -> 它在数组里的下标
遍历到 nums[i] = x：
    need = target - x
    need 在 seen 里  ->  seen[need] 与 i 就是答案
    否则              ->  记下 seen[x] = i，留给后面的数来配

先查后存是这份写法的关键：查询发生时，表里只有下标严格小于 i 的元素， x 自己还没进表。由此免费得到题目要求的「不能使用两次相同的元素」，不需要任何额外判断。

数据规模与复杂度¶

2 <= n <= 1e4，元素与 target 都在 1e9 量级（Python 整数不会溢出， target - x 随便减）。一遍扫描，每步做一次 O(1) 的字典查与写，时间 O(n)、空间 O(n)。双重循环是 n 的平方除以二 = 5e7 次比较，1e4 的规模下勉强能过，但题面「进阶」明确要求复杂度小于 O(n^2)，哈希表是标准答案。

坑在哪¶

顺序不能颠倒成「先存后查」。target 恰为某个元素的两倍时（如 nums = [3, 3] 之外的 nums = [3, 1]、target = 6），先把 nums[i] 存进表再查 need，它会查到刚写进去的自己，返回 [i, i] 这种同一个元素用两次的非法答案。
同一个值出现多次时，表里只保留最后一次出现的下标。题目保证答案唯一，被覆盖掉的旧下标不会是答案的一部分，所以不必把下标存成列表。 nums = [3, 3]、target = 6 能过正是因为查在存之前：i=1 时表里还是 {3: 0}。
判题按 unordered 比对——题面原文「你可以按任意顺序返回答案」， [0, 1] 与 [1, 0] 都算对。但顺序放宽不等于内容放宽：下标必须恰好是这两个，多吐一个或吐错一个照样判错。
末尾的空列表只是兜底。题目保证「只会存在一个有效答案」，循环里必然 return；删掉这一行则无解时函数隐式返回 None，判题拿到的不是列表，直接报类型错误。

样例复核¶

nums = [3, 2, 4]，target = 6。

i=0  x=3  need=3  表空，没命中      ->  seen = {3: 0}
i=1  x=2  need=4  没命中            ->  seen = {3: 0, 2: 1}
i=2  x=4  need=2  命中 seen[2] = 1  ->  返回 [1, 2]

与样例输出一致。注意 i=0 那步：若先存后查，need=3 会命中自己，错成 [0, 0]。

参考实现¶

solutions/leetcode/LC1/sol.py
from typing import List, Optional


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 值 -> 下标。只装扫过的元素，这是「先查后存」能免掉重复使用判断的前提
        seen = {}
        for i, x in enumerate(nums):
            # 搭档的值被 x 唯一确定，于是找搭档退化成一次查表
            need = target - x
            # 先查：此刻表里全是下标小于 i 的元素，绝不会配到 x 自己
            if need in seen:
                return [seen[need], i]
            # 后存：当前元素留给后面的数来配。同值覆盖旧下标不影响正确性，
            # 因为题目保证答案唯一
            seen[x] = i
        return []                       # 题目保证有解，正常走不到这里；留着是为了返回类型稳定

LC1 两数之和¶