两数之和

问题拆解

给定一个整数数组 nums 和目标值 target，需要找到两个不同位置的数，让它们之和等于目标值。

暴力做法会枚举所有数对，时间复杂度是 $O(n^2)$。真正值得抓住的问题是：当遍历到 x 时，我们只需要知道 target - x 是否已经出现过。

把“寻找另一个数”换成“查询另一个数”，哈希表正好适合做这件事。

一次遍历

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

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

为什么先查询再写入？因为题目要求不能重复使用同一个元素。如果先放入当前数字，当 target == value * 2 时，就可能错误地匹配到自己。

复杂度

指标	复杂度	原因
时间	$O(n)$	数组只遍历一次
空间	$O(n)$	最坏情况下保存所有元素

可以迁移的模式

• 题目要求快速判断“某个值是否出现过”；
• 需要保存“值 → 位置”或“值 → 次数”的映射；
• 一边遍历，一边利用之前的信息完成当前决策。

下次看到“配对”“补数”“是否存在”这些词，可以先想想哈希表。