两数之和
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²)。瓶颈在内层——每固定一个 x,都要重新扫一遍数组去找它的另一半。
正解:边扫描边建哈希表。
① 定义历史状态:seen 保存“已经扫描过的值 → 下标”,只代表当前位置左侧。
② 计算补数:当前值为 x 时,只需查询 need=target-x,把重复线性查找降为 O(1)。
③ 先查后存:命中就返回 [seen[need], index];未命中才写入当前值,因此同一元素不会自配。
④ 非平凡样例:[3,3], target=6 中,第一个 3 查空表后写入,第二个 3 才命中前一个下标。
取舍:哈希法用 O(n) 空间把时间从 O(n²) 降到 O(n);若数组已排序,也可双指针 O(1) 额外空间,但本题还要返回原下标,需额外保留下标映射。
target=2x(如 [3,3],6)会把刚存进去的自己当成另一半,错误返回 [i,i]。② 哈希表存的是「值 → 下标」而非「下标 → 值」,因为要拿补数的值去反查它的下标。
③ 若数组有重复值,后写的下标会覆盖先写的——本题保证唯一解、只需任一组下标,无妨;但若要返回所有配对就不能简单覆盖。
3 · 图解
里程碑① 主例开始:nums=[2,7,11,15],target=9,seen={}
里程碑② i=0,x=2:need=7 未命中;本轮结束 seen={2:0}
里程碑③ i=1,x=7:need=2 命中历史下标 0;返回 [0,1]
里程碑④ 重复值例 [3,3]:第一个 3 先查空表,再写 seen={3:0}
里程碑⑤ 第二个 3 查询时尚未写入自身,只会命中下标 0,不会得到 [1,1]
| 阶段 | 输入现场 | 补数 | 查询时 seen | 判定与动作 |
|---|---|---|---|---|
| 0 | 主例初始化 | — | {} | 等待扫描 |
| 1 | 主例 i=0,x=2 | 7 | {} | 未命中,轮末写入 {2:0} |
| 2 | 主例 i=1,x=7 | 2 | {2:0} | 命中并返回 [0,1] |
| 3 | 重复值例 i=0,x=3 | 3 | {} | 先查未命中,再写入 {3:0} |
| 4 | 重复值例 i=1,x=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) 空间换来一个数量级的时间提升。
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](先查后存保证不选到自身)。