两数之和
LC 1 ↗1 · 题目
要完成的任务
给定整数数组 nums 和整数 target,找出两个不同位置,使这两个位置上的数之和等于 target,返回它们的下标。答案中的两个下标可按任意顺序排列。
字段与保证
nums[i] 是下标 i 处的整数;同一个数组元素不能重复使用。题目保证每组输入恰好存在一个有效答案。
全部示例
示例 1:nums=[2,7,11,15], target=9 → [0,1],因为 nums[0]+nums[1]=9。
示例 2:nums=[3,2,4], target=6 → [1,2]。
示例 3:nums=[3,3], target=6 → [0,1];两个 3 来自不同下标。
约束与进阶
2 ≤ nums.length ≤ 104。-109 ≤ nums[i], target ≤ 109。- 只存在一个有效答案;进阶要求设计时间复杂度低于 O(n²) 的算法。
2 · 思路(暴力→最优)
暴力起手:双层循环枚举所有下标对 (i, j),判 nums[i] + nums[j] == target,O(n²)。慢的根源:外层每固定一个数,内层都要重新把数组扫一遍去找它的另一半——前面扫过的元素明明都"见过",却没留下任何可直接查询的记录,同一批元素被一遍遍重扫。
① 关键转化——把"枚举数对"换成"枚举单数 + 查另一半":当前值 value 一固定,另一半根本不用枚举——它被等式唯一确定为 complement = target - value。于是每轮真正的问题只剩一个:complement 这个值之前出现过吗?在哪个下标?这正是字典「值 → 下标」的 O(1) 拿手活,n² 次数对验证退化成 n 次 O(1) 查询。这套「存我见过的、查我需要的」模式,也是 LC560 查「前缀和 − k」的底层零件。
② 只查左边为什么不漏:常见困惑——seen 只装当前位置左侧的元素,万一我的另一半在右边呢?不漏:设答案是 (i, j) 且 i < j,扫到 j 时 i 必然已写入 seen。每一对都在它靠后的那个成员处被发现,恰好一次——所以每个数只需对"左边"负责,单向一趟就覆盖全部数对。
③ 三个量的身份:
| 代码里的量 | 它在题里是谁 | 提供什么 |
|---|---|---|
seen | 当前位置左侧已扫元素的「值 → 下标」映射 | O(1) 回答"某值出现过没有、在哪";查询时刻不含当前值自己 |
complement = target - value | 当前值缺的那"另一半"的值 | 只当查询的 key,本身不写入表 |
index / value | 当前候选=配对里靠后的成员 | 命中时与 seen[complement] 组成答案 |
④ "先查后存"从身份表直接推出:seen 的身份是"左侧世界",那么第 index 轮查询时它就不能含 value 自己——写入必须放在查询之后。这一个顺序同时解决了"同一元素不能用两次":当 target = 2 × value 时,查 complement 只可能命中左边的同值元素,绝不会命中自己;反过来"先存后查"就是把自己也放进了候选。
⑤ 用样例验证关键一步:[3,3], target=6:i=0 查 complement=3,seen 还是空表 → 未命中,写入 {3:0};i=1 再查 complement=3 → 命中下标 0,返回 [0,1]。两个 3 来自不同下标,顺序对了就天然不自配。多解法取舍:若数组已排序可用对撞双指针省掉 O(n) 空间,但本题输入未排序且要原下标,哈希一趟最直接(细节见段5追问)。
seen[value] = index 再查 complement。最小反例 [3,3], target=6:i=0 就命中刚写入的自己,错误返回 [0,0],真值 [0,1]。② 映射方向存反成「下标 → 值」(
seen[index] = value):查 complement in seen 时对照的是下标集合。最小反例 [2,7], target=9:i=1 查"2 在不在 key 里",key 只有 {0},未命中,错误返回 [],真值 [0,1]。③ 两趟法(先全存再查)忘排除自身:不判
seen[complement] != i。最小反例 [3,2,4], target=6:全存后 seen={3:0, 2:1, 4:2},i=0 查 complement=3 命中自己,错误返回 [0,0],真值 [1,2]。一趟"先查后存"天然免掉这个判断。3 · 图解
里程碑① 主例开始:nums=[2,7,11,15],target=9,seen={}
里程碑② i=0,value=2:complement=7 未命中;本轮结束 seen={2:0}
里程碑③ i=1,value=7:complement=2 命中历史下标 0;返回 [0,1]
里程碑④ 重复值例 [3,3]:第一个 3 先查空表,再写 seen={3:0}
里程碑⑤ 第二个 3 查询时尚未写入自身,只会命中下标 0,不会得到 [1,1]
| 阶段 | 输入现场 | 补数 | 查询时 seen | 判定与动作 |
|---|---|---|---|---|
| 0 | 主例初始化 | — | {} | 等待扫描 |
| 1 | 主例 i=0,value=2 | 7 | {} | 未命中,轮末写入 {2:0} |
| 2 | 主例 i=1,value=7 | 2 | {2:0} | 命中并返回 [0,1] |
| 3 | 重复值例 i=0,value=3 | 3 | {} | 先查未命中,再写入 {3:0} |
| 4 | 重复值例 i=1,value=3 | 3 | {3:0} | 命中下标 0,返回 [0,1],不会自配 |
4 · 代码
class Solution:
def twoSum(self, nums, target):
# 1. seen 只保存当前位置之前的“值 → 下标”
seen = {}
# 2. 每轮先查补数,未命中再记录当前值
for index, value in enumerate(nums):
complement = target - value
if complement in seen:
return [seen[complement], index]
seen[value] = index
return []5 · 复杂度
时间 O(n),每个元素做一次补数查询并至多写入哈希一次;空间 O(n),最坏存下几乎所有元素——用 O(n) 空间换掉暴力 O(n²) 里被重复扫描的时间。高频追问一:"数组已排序还用哈希吗?"——排序数组可对撞双指针,O(n) 时间、O(1) 额外空间;但本题要返回原下标,若自己排序就得先绑定 (值, 原下标) 再排,O(n) 空间并没省下来,未排序输入直接哈希一趟最划算。追问二:"哈希查询一定是 O(1) 吗?"——是均摊/期望 O(1),极端冲突下单次会退化,面试口径答"均摊 O(1)";要最坏保证可换平衡树,查询 O(log n)。
6 · 测试用例
功能:[2,7,11,15],9 → [0,1];边界:最短两元素 [3,3],6 → [0,1](重复值也要能命中);特殊:含负数 [-1,-2,-3],-5 → [1,2]、目标依赖后面元素 [3,2,4],6 → [1,2](先查后存保证不选到自身)。