一、题目描述
原题
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1]
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
约束条件
2 <= nums.length <= 10⁴-10⁹ <= nums[i] <= 10⁹-10⁹ <= target <= 10⁹- 只会存在一个有效答案
二、题目解析
核心问题拆解
| 关键点 | 分析 |
|---|---|
| 输入 | 整数数组 + 目标值 |
| 输出 | 两个数的下标（不是数值本身） |
| 约束 | 同一元素不能使用两次 |
| 保证 | 有且仅有一个解 |
思考方向
flowchart LR A[原问题] –> B[“nums[i] + nums[j] = target”] B –> C[转化思维] C –> D[“对于每个 nums[i]<br/>寻找 target – nums[i]”] D –> E[如何快速查找?] E –> F[“哈希表 O(1)”]
三、算法解答
算法一：暴力枚举法
1. 算法原理描述
核心思想：穷举所有可能的两数组合，检查它们的和是否等于目标值。
实现方式：
- 使用两层循环
- 外层循环固定第一个数
nums[i] - 内层循环遍历其后的所有数
nums[j]（j > i） - 检查
nums[i] + nums[j] == target
2. 算法解答过程
以 nums = [2, 7, 11, 15], target = 9 为例：
| 外层 i | 内层 j | nums[i] | nums[j] | 和 | 是否等于 target |
|---|---|---|---|---|---|
| 0 | 1 | 2 | 7 | 9 | 找到！ |
返回 [0, 1]
3. 算法原理图像解析
flowchart TD subgraph 数组[“数组 nums, target = 9”] A0[“[0]=2”] — A1[“[1]=7”] — A2[“[2]=11”] — A3[“[3]=15”] end subgraph 流程[“暴力枚举流程”] S[开始] –> L1[“外层循环 i = 0”] L1 –> L2[“内层循环 j = 1”] L2 –> C1{“nums[0] + nums[1]<br/>= 2 + 7 = 9<br/>== target?”} C1 –>|” 是”| R[“返回 [0, 1]”] C1 –>|” 否”| L3[“j++, 继续内层”] L3 –> L4[“若内层结束<br/>i++, 继续外层”] end subgraph 复杂度[“复杂度分析”] T[“⏱ 时间: O(n²)”] SP[” 空间: O(1)”] end
4. 算法代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int n = nums.size();
// 外层循环：固定第一个数
for (int i = 0; i < n - 1; i++) {
// 内层循环：遍历第一个数之后的所有数
for (int j = i + 1; j < n; j++) {
// 检查两数之和是否等于目标值
if (nums[i] + nums[j] == target) {
return {i, j};
}
}
}
// 题目保证有解，这里不会执行到
return {};
}
};
5. 复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n²) | 两层嵌套循环，最坏情况遍历 n(n-1)/2 次 |
| 空间复杂度 | O(1) | 只使用常数额外空间 |
6. 使用范围
| 场景 | 适用性 |
|---|---|
| 数据规模小（n < 1000） | 适用 |
| 数据规模大 | 会超时 |
| 对空间要求极高 | 适用 |
| 面试中作为初始解法 | 适用，但需优化 |
算法二：哈希表法（一遍哈希）⭐ 最优解
1. 算法原理描述
核心思想：将「寻找两数之和」转化为「寻找差值」问题。
关键转换：
nums[i] + nums[j] = target
↓ 转化
nums[j] = target - nums[i]
实现方式：
- 使用哈希表存储已遍历过的元素及其下标
- 对于当前元素
nums[i]，计算complement = target - nums[i] - 在哈希表中查找
complement是否存在 - 若存在，说明找到答案；若不存在，将当前元素加入哈希表
优势：哈希表的查找时间复杂度为 O(1)，整体只需一次遍历。
2. 算法解答过程
以 nums = [2, 7, 11, 15], target = 9 为例：
| 步骤 | 当前元素 | complement | 哈希表查找 | 操作 | 哈希表状态 |
|---|---|---|---|---|---|
| 1 | nums[0]=2 | 9-2=7 | 7 不存在 | 存入 | |
| 2 | nums[1]=7 | 9-7=2 | 2 存在！下标0 | 返回 [0,1] | – |
3. 算法原理图像解析
flowchart TD subgraph 输入[“输入: nums = [2,7,11,15], target = 9”] direction LR N0[“2”] –> N1[“7”] –> N2[“11”] –> N3[“15”] end subgraph Step1[“步骤1: 处理 nums[0] = 2”] S1A[“计算 complement = 9 – 2 = 7”] S1B{“哈希表中<br/>查找 7″} S1C[” 未找到”] S1D[“存入哈希表<br/>{2: 0}”] S1A –> S1B –> S1C –> S1D end subgraph Step2[“步骤2: 处理 nums[1] = 7”] S2A[“计算 complement = 9 – 7 = 2”] S2B{“哈希表中<br/>查找 2″} S2C[” 找到! 下标=0″] S2D[“返回 [0, 1]”] S2A –> S2B –> S2C –> S2D end 输入 –> Step1 –> Step2 subgraph 要点[” 核心要点”] K1[“边遍历边建表”] K2[“先查找再存入”] K3[“O(1) 查找”] end
哈希表状态变化：
flowchart LR subgraph T1[“初始状态”] E1[“空 ∅”] end subgraph T2[“处理2后”] H1[“2 → 0”] end subgraph T3[“处理7时”] H2[“2 → 0”] F[“查找2 “] end T1 –>|”存入 2:0″| T2 –>|”查找2″| T3
4. 算法代码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 哈希表：key = 数值，value = 下标
unordered_map<int, int> hashMap;
for (int i = 0; i < nums.size(); i++) {
// 计算当前元素的"配对值"
int complement = target - nums[i];
// 在哈希表中查找配对值
if (hashMap.find(complement) != hashMap.end()) {
// 找到了！返回两个下标
return {hashMap[complement], i};
}
// 未找到，将当前元素存入哈希表
hashMap[nums[i]] = i;
}
// 题目保证有解，这里不会执行到
return {};
}
};
5. 代码详解
// 关键点解析：
// 1. 为什么用 unordered_map 而不是 map？
// - unordered_map 基于哈希表，查找/插入 O(1)
// - map 基于红黑树，查找/插入 O(log n)
// 2. 为什么先查找再存入？
// - 避免同一元素被使用两次
// - 例如：nums = [3, 3], target = 6
// - 第一个3存入后，第二个3能找到第一个3
// 3. hashMap.find() vs hashMap.count()
// - find() 返回迭代器，未找到返回 end()
// - count() 返回 0 或 1
// - 两种写法都可以，find() 更常用
6. 复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n) | 只需遍历数组一次，哈希表操作 O(1) |
| 空间复杂度 | O(n) | 最坏情况需存储 n-1 个元素 |
7. 使用范围
| 场景 | 适用性 |
|---|---|
| 数据规模大 | 最优解 |
| 需要快速查找 | O(1) 查找 |
| 对空间敏感 | ️ 需要额外空间 |
| 需要返回下标 | 适用 |
| 数组无序 | 适用 |
算法三：排序 + 双指针法（特殊场景）
️ 注意：此方法会丢失原始下标，需要额外处理。仅适用于返回值而非下标的变体题目。
1. 算法原理描述
核心思想：利用有序数组的性质，使用双指针从两端向中间逼近。
实现方式：
- 将数组排序
- 设置左指针
left = 0，右指针right = n-1 - 计算
sum = nums[left] + nums[right]- 若
sum == target：找到答案 - 若
sum < target：左指针右移（增大和） - 若
sum > target：右指针左移（减小和）
- 若
2. 算法解答过程
以 nums = [2, 7, 11, 15], target = 9 为例（已排序）：
| 步骤 | left | right | nums[left] | nums[right] | sum | 与target比较 | 操作 |
|---|---|---|---|---|---|---|---|
| 1 | 0 | 3 | 2 | 15 | 17 | 17 > 9 | right– |
| 2 | 0 | 2 | 2 | 11 | 13 | 13 > 9 | right– |
| 3 | 0 | 1 | 2 | 7 | 9 | 9 == 9 | 找到 |
3. 算法原理图像解析
flowchart TD subgraph 初始[“排序后数组: [2, 7, 11, 15], target = 9”] direction LR A[“2”] — B[“7”] — C[“11”] — D[“15”] end subgraph R1[“第1轮”] R1L[“L→2”] R1R[“15←R”] R1C[“2 + 15 = 17 > 9”] R1A[“R左移 ←”] R1L — R1R R1C –> R1A end subgraph R2[“第2轮”] R2L[“L→2”] R2R[“11←R”] R2C[“2 + 11 = 13 > 9”] R2A[“R左移 ←”] R2L — R2R R2C –> R2A end subgraph R3[“第3轮 “] R3L[“L→2”] R3R[“7←R”] R3C[“2 + 7 = 9 == 9”] R3A[“找到答案!”] R3L — R3R R3C –> R3A end 初始 –> R1 –> R2 –> R3
双指针移动规则：
flowchart TD S[“计算 sum = nums[L] + nums[R]”] –> C{sum 与 target 比较} C –>|”sum == target”| F[” 找到答案”] C –>|”sum < target”| L[“L++ 需要更大的数”] C –>|”sum > target”| R[“R– 需要更小的数”] L –> S R –> S
4. 算法代码
// 方法：保留原始下标的双指针解法
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// 创建副本并排序，保留原始下标
vector<pair<int, int>> numWithIndex;
for (int i = 0; i < nums.size(); i++) {
numWithIndex.push_back({nums[i], i});
}
sort(numWithIndex.begin(), numWithIndex.end());
int left = 0, right = nums.size() - 1;
while (left < right) {
int sum = numWithIndex[left].first + numWithIndex[right].first;
if (sum == target) {
return {numWithIndex[left].second, numWithIndex[right].second};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return {};
}
};
5. 复杂度分析
| 复杂度类型 | 值 | 说明 |
|---|---|---|
| 时间复杂度 | O(n log n) | 排序 O(n log n) + 双指针 O(n) |
| 空间复杂度 | O(n) | 需要存储原始下标 |
6. 使用范围
| 场景 | 适用性 |
|---|---|
| 数组已排序 | 最佳选择 |
| 返回值而非下标 | 适用 |
| 需要返回下标 | ️ 需额外处理 |
| Two Sum II（有序数组） | 标准解法 |
四、三种算法对比
flowchart LR subgraph 暴力法[“暴力枚举”] B1[“⏱ O n²”] B2[” O 1″] B3[“⭐⭐”] end subgraph 哈希表[“哈希表法 推荐”] H1[“⏱ O n”] H2[” O n”] H3[“⭐⭐⭐⭐⭐”] end subgraph 双指针[“排序+双指针”] D1[“⏱ O n log n”] D2[” O n”] D3[“⭐⭐⭐”] end 暴力法 –>|”优化查找”| 哈希表 暴力法 –>|”有序场景”| 双指针
| 算法 | 时间复杂度 | 空间复杂度 | 适用场景 | 推荐指数 |
|---|---|---|---|---|
| 暴力枚举 | O(n²) | O(1) | 小数据、空间受限 | ⭐⭐ |
| 哈希表法 | O(n) | O(n) | 通用最优解 | ⭐⭐⭐⭐⭐ |
| 排序+双指针 | O(n log n) | O(n) | 有序数组、返回值 | ⭐⭐⭐ |
面试建议
flowchart LR A[“1️⃣ 先说暴力解法”] –> B[“2️⃣ 分析瓶颈<br/>重复查找”] B –> C[“3️⃣ 引出哈希表优化”] C –> D[“4️⃣ 给出最优解”]
五、知识点总结
1. 涉及的数据结构
| 数据结构 | 用途 | 关键操作 |
|---|---|---|
| 数组 | 存储原始数据 | 遍历 O(n) |
| 哈希表 | 快速查找 | 查找/插入 O(1) |
2. 涉及的算法思想
mindmap root((两数之和<br/>核心思想)) 暴力枚举 穷举所有可能 基础解法 空间换时间 用额外空间 降低时间复杂度 问题转化 找和转找差 核心优化思路 双指针 有序数组 两端逼近
3. C++ 知识点
// 1. unordered_map 的使用
#include <unordered_map>
unordered_map<int, int> map;
map[key] = value; // 插入
map.find(key); // 查找，返回迭代器
map.count(key); // 返回 0 或 1
map.end(); // 结束迭代器
// 2. vector 的初始化返回
return {a, b}; // 直接返回初始化列表
// 3. pair 的使用
pair<int, int> p = {value, index};
p.first; // 第一个元素
p.second; // 第二个元素
六、做题模板
「两数之和」类问题通用模板
/*
* 两数之和问题模板
* 适用于：在数组中寻找满足 nums[i] + nums[j] = target 的配对
*/
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// Step 1: 创建哈希表
// key: 数组元素值
// value: 元素下标
unordered_map<int, int> hashMap;
// Step 2: 遍历数组
for (int i = 0; i < nums.size(); i++) {
// Step 3: 计算配对值
int complement = target - nums[i];
// Step 4: 在哈希表中查找配对值
if (hashMap.find(complement) != hashMap.end()) {
// 找到配对，返回结果
return {hashMap[complement], i};
}
// Step 5: 将当前元素加入哈希表
hashMap[nums[i]] = i;
}
// Step 6: 未找到（题目保证有解时不会执行）
return {};
}
};
模板流程图：
flowchart TD A[开始] –> B[“创建空哈希表”] B –> C[“遍历数组 i = 0 to n-1”] C –> D[“计算 complement = target – nums[i]”] D –> E{“complement<br/>在哈希表中?”} E –>|”是”| F[“返回 hashMap[complement], i”] E –>|”否”| G[“hashMap[nums[i]] = i”] G –> H{“i < n-1?”} H –>|”是”| C H –>|”否”| I[“返回空 无解”]
模板变体
变体1：返回所有配对
vector<vector<int>> twoSumAll(vector<int>& nums, int target) {
unordered_map<int, vector<int>> hashMap; // 存储所有下标
vector<vector<int>> result;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (hashMap.count(complement)) {
for (int j : hashMap[complement]) {
result.push_back({j, i});
}
}
hashMap[nums[i]].push_back(i);
}
return result;
}
变体2：有序数组（双指针）
vector<int> twoSumSorted(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return {left, right}; // 注意：这里返回的是下标
} else if (sum < target) {
left++;
} else {
right--;
}
}
return {};
}
七、相关题目推荐
flowchart TD A[“1. 两数之和”] –> B[“167. 两数之和 II<br/>有序数组”] A –> C[“15. 三数之和”] C –> D[“18. 四数之和”] A –> E[“454. 四数相加 II”]
| 题号 | 题目 | 难度 | 关联知识点 |
|---|---|---|---|
| 167 | 两数之和 II – 输入有序数组 | 中等 | 双指针 |
| 15 | 三数之和 | 中等 | 双指针 + 去重 |
| 18 | 四数之和 | 中等 | 递归 + 双指针 |
| 454 | 四数相加 II | 中等 | 哈希表分组 |
八、面试高频问答
Q1: 为什么哈希表法要先查找再存入？
答：为了避免同一元素被使用两次。例如 nums = [3], target = 6，如果先存入再查找，会错误地返回 [0, 0]。
Q2: 如果有多个答案怎么办？
答：题目保证只有一个答案。若需返回所有答案，需要使用 unordered_map<int, vector<int>> 存储所有下标。
Q3: 哈希表 vs 红黑树（map vs unordered_map）？
答：
unordered_map：哈希表，查找 O(1)，无序map：红黑树，查找 O(log n)，有序
本题不需要有序，选择 unordered_map 更优。
Q4: 时间复杂度 O(n) 是最优吗？
答：是的。至少需要遍历一次数组才能确定答案，O(n) 是下界。
九、一图总结
flowchart TB subgraph 题目[” 题目: 两数之和”] Q[“找两个数 和为target<br/>返回下标”] end subgraph 思路[” 核心思路”] T[“找和转找差<br/>nums[j] = target – nums[i]”] end subgraph 解法[” 最优解法”] S1[“哈希表存储已遍历元素”] S2[“O 1 查找配对值”] S3[“边遍历边建表”] end subgraph 复杂度[” 复杂度”] C1[“时间: O n”] C2[“空间: O n”] end subgraph 记忆[” 记忆口诀”] M[“两数之和哈希表<br/>边查边存是关键<br/>先找差值后存入<br/>一次遍历搞定它”] end 题目 –> 思路 –> 解法 –> 复杂度 –> 记忆
![表情[baoquan]-拾光赋](https://blogs.ink/wp-content/themes/zibll/img/smilies/baoquan.gif)
暂无评论内容