问题描述
给定一个整数数组nums和一个整数目标值target，在数组中找出和为目标值的两个整数，并返回它们的数组下标。题目保证只有一个有效答案，且不能使用两次相同的元素。
解题思路
1. 暴力解法：双重循环
- 核心思想：遍历数组中的每个元素，再遍历其后的所有元素，检查两数之和是否等于
target。 - 时间复杂度：O(n²)（n为数组长度，最坏情况下需遍历n*(n-1)/2次）。
- 空间复杂度：O(1)（无需额外空间）。
- 示例代码：
vector<int> twoSum(vector<int>& nums, int target) { int n = nums.size(); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { if (nums[i] + nums[j] == target) { return {i, j}; } } } return {}; // 题目保证有解，实际不会执行 }2. 哈希表优化：空间换时间
- 核心思想：使用哈希表（
unordered_map）存储已遍历元素的值和下标，遍历数组时，计算当前元素与target的差值complement，若complement存在于哈希表中，则直接返回两个下标；否则将当前元素存入哈希表。 - 时间复杂度：O(n)（仅需遍历一次数组，哈希表查询时间为O(1)）。
- 空间复杂度：O(n)（最坏情况下需存储n-1个元素）。
- 示例代码：
#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> numMap; / /key: 元素值，value: 下标
for (int i = 0; i < nums.size(); ++i) {
int complement = target - nums[i];
if (numMap.find(complement) != numMap.end()) {
return {numMap[complement], i}; // 返回已存下标和当前下标
}
numMap[nums[i]] = i; // 存入当前元素
}
return {}; // 题目保证有解，实际不会执行 }
}；
方法对比
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 暴力解法 | O(n²) | O(1) | 数组规模较小（n<1000） |
| 哈希表优化 | O(n) | O(n) | 数组规模较大（n≥1000） |
注意事项
- 元素唯一性：题目要求“不能使用两次相同的元素”，因此哈希表存储的是已遍历元素，避免重复使用当前元素（如示例3中的
[3,3]，第一个3存入哈希表后，第二个3计算complement=3时，直接返回两个下标）。 - 返回顺序：哈希表中存储的是已遍历元素的下标，因此返回时需先返回哈希表中的下标（如示例2中的
[3,2,4]，遍历到2时，complement=4不存在，存入2→1；遍历到4时，complement=2存在，返回[1,2]）。
总结
两数之和问题的最优解是哈希表优化法，通过空间换时间将时间复杂度从O(n²)降至O(n)，适用于大多数场景。暴力解法虽然简单，但效率较低，仅适用于小规模数据。在实际开发中，应优先选择哈希表优化法，以提升程序性能。
 ✨| RandomChoicePicker（标签生成）)
