两数之和

示例 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 \le nums.length \le 10^4$
• $-10^9 \le nums[i] \le 10^9$
• $-10^9 \le target \le 10^9$
• 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 $O(n^2)$ 的算法吗？

错误分析与改进#

1. 输入方式：LeetCode 不需要手动 cin 输入，nums 和 target 是函数参数。
2. 元素数量获取：sizeof(nums) 返回的是 vector 对象本身的大小，应使用 nums.size() 获取元素个数。
3. 循环变量控制：内层循环的更新应该是 j++ 而不是 i++。
4. 提前返回：return nums[j] 会在找到结果前提前退出函数。
5. 返回值语法：C++ 中返回 vector 应使用花括号 {}（如 return {i, j}）。
6. 输出与逗号表达式：cout 不支持此类写法，且 LeetCode 不需要输出结果。
7. 重复使用元素：内层循环 j 应该从 i + 1 开始，以避免“同一个元素被使用两次”的问题。

优化的暴力解法#

1
class Solution {
2
public:
3
    vector<int> twoSum(vector<int>& nums, int target) {
4
        for (int i = 0; i < nums.size(); i++) {
5
            for (int j = i + 1; j < nums.size(); j++) {
6
                if(nums[j] + nums[i] == target) {
7
                    return {i, j};
8
                }
9
            }
10
        }
11
        return {};
12
    }
13
};

运行结果：

• 执行用时：95ms
• 消耗内存：13.70MB

优化版源码#

1
#include <vector>
2
#include <unordered_map>
3
using namespace std;
4

5
class Solution {
6
public:
7
    vector<int> twoSum(vector<int>& nums, int target) {
8
        unordered_map<int, int> numToIndex;      // 创建哈希表：数值 -> 下标
9

10
        for (int i = 0; i < nums.size(); ++i) {  // 只需要遍历一次
11
            int complement = target - nums[i];   // 计算满足条件的另一个数
12

13
            if (numToIndex.count(complement)) {  // 在 O(1) 内查找补数是否存在
14
                return {numToIndex[complement], i};
15
            }
16

17
            numToIndex[nums[i]] = i;             // 将当前数值存入，供后续查用
18
        }
19
        return {};
20
    }
21
};

运行结果：

• 执行用时：4ms
• 消耗内存：14.57MB

关键点总结#

• unordered_map：查找平均复杂度为 O(1)。
• 时间复杂度：从 O(n²) 降至 O(n)。
• 空间复杂度：为 O(n)，用于维护哈希表。