给定一个整数数组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⁹- 只会存在一个有效答案
二、题目解析
核心问题拆解
| 关键点 | 分析 |
|---|---|
| 输入 | 整数数组 + 目标值 |
| 输出 | 两个数的下标（不是数值本身） |
| 约束 | 同一元素不能使用两次 |
| 保证 | 有且仅有一个解 |
思考方向
原问题
nums[i] + nums[j] = target
转化思维
对于每个 nums[i]
寻找 target - nums[i]
如何快速查找?
哈希表 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. 算法原理图像解析
复杂度分析
⏱ 时间: O(n²)
💾 空间: O(1)
暴力枚举流程
✅ 是
❌ 否
开始
外层循环 i = 0
内层循环 j = 1
nums[0] + nums[1]
= 2 + 7 = 9
== target?
返回 [0, 1]
j++, 继续内层
若内层结束
i++, 继续外层
数组 nums, target = 9
[0]=2
[1]=7
[2]=11
[3]=15
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. 算法原理图像解析
🔑 核心要点
边遍历边建表
先查找再存入
O(1) 查找
步骤2: 处理 nums[1] = 7
计算 complement = 9 - 7 = 2
哈希表中
查找 2
✅ 找到! 下标=0
返回 [0, 1]
步骤1: 处理 nums[0] = 2
计算 complement = 9 - 2 = 7
哈希表中
查找 7
❌ 未找到
存入哈希表
{2: 0}
输入: nums = [2,7,11,15], target = 9
2
7
11
15
哈希表状态变化：
存入 2:0
查找2
处理7时
2 → 0
查找2 ✅
处理2后
2 → 0
初始状态
空 ∅
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 个元素 |
