1. 两数之和（简单）

Blind 75 › 1. 两数之和（简单） （第 3 章）
文章工具

题目

给一个整数数组 nums 和一个整数 target，找出数组里两个相加等于 target 的数，返回它们的下标。

规则：保证有且只有一组答案；同一个元素不能重复用；两个下标按任意顺序返回都行。

自造示例：nums = [1, 4, 7, 9], target = 13 → [1, 3]。因为 nums[1] + nums[3] = 4 + 9 = 13。

约束：数组长度 2 ~ 104；nums[i]、target 都在 -109 ~ 109；保证恰好一个答案。

思路

一句话：一边扫数组，一边把「前面见过的数」记进哈希表；走到每个数时，先查它的“补数”在不在表里。

最直白的想法：枚举所有下标对 (i, j)（i < j），看 nums[i] + nums[j] 是否等于 target。这要两层循环，时间 O(n²)；n = 104 时接近 5000 万次比较，Python 会明显吃力。

关键观察：走到某个数 x 时，我们不需要再回头和每个数两两相加，只需要回答一个问题——前面有没有出现过 target - x？这正是哈希表擅长的：记下“值 → 下标”，一次查询 O(1)。

于是可以一趟遍历完成：查补数、查到就返回，查不到就把当前数存进表。对于任意答案对 (i, j)（设 i < j），扫到 j 时 i 一定已经入库，必然能被找到。

解法

用哈希表 seen[值] = 下标，遍历一遍：

  1. 当前数是 x，计算补数 need = target - x。
  2. 如果 need 在 seen 里，说明前面出现过它，返回 [seen[need], 当前下标]。
  3. 否则把 x 与当前下标存入 seen，继续。
下标 i当前数 x补数 13 – x查询前的哈希表动作
0112{}查不到，存 1 → 0
149{1:0}查不到，存 4 → 1
276{1:0, 4:1}查不到，存 7 → 2
394{1:0, 4:1, 7:2}查到 4 → 1，返回 [1, 3]

整个过程只扫一遍，且每次只做一次 O(1) 的查找和插入。

下图把上面 3 个步骤串成流程，并逐步演示：

1. 两数之和（简单） 解法步骤流程图
图① 解法步骤流程图（共 3 步）。
1. 两数之和（简单） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Solution {
public:
 vector<int> twoSum(vector<int>& nums, int target) {
 unordered_map<int, int> seen;   // 值 -> 下
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。