1. 两数之和

题目

力扣题目 给定一个整数数组 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 \le nums.length \le 10^4$
• $-10^9 \le nums[i] \le 10^9$
• $-10^9 \le target \le 10^9$
• 只会存在一个有效答案

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

考察内容

• 数组的遍历与下标操作
• 哈希表 unordered_map 的查找和插入
• 空间换时间的优化思想
• 如何避免重复使用同一个元素

解题思路

暴力法

使用两层循环枚举数组中的所有二元组：外层循环确定第一个数，内层循环从 i + 1 开始寻找第二个数。如果两个数之和等于 target，就返回它们的下标。

内层循环从 i + 1 开始有两个作用：

1. 避免将同一个元素使用两次；
2. 避免重复检查 (i, j) 和 (j, i)。

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

哈希表法

对于当前元素 nums[i]，要使两个数的和等于 target，需要寻找的另一个数为：

使用哈希表保存已经遍历过的元素，键为元素值，值为元素下标。每次遍历到 nums[i] 时：

1. 计算它的补数 target - nums[i]；
2. 检查补数是否已经存在于哈希表中；
3. 如果存在，返回补数的下标和当前下标；
4. 如果不存在，将当前元素及其下标存入哈希表。

这里需要先查找、后插入。否则当 target == 2 * nums[i] 时，可能错误地重复使用当前元素。

• 时间复杂度：$O(n)$，哈希表的查找和插入平均为 $O(1)$
• 空间复杂度：$O(n)$

例如 nums = [3, 2, 4]，target = 6：

代码演示

// 常规暴力法
std::vector<int> twoSum(std::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 {};
}

// 哈希表版本
std::vector<int> twoSumHash(std::vector<int>& nums, int target) {
    int n = nums.size();
    std::unordered_map<int, int> hash_table;
    for (int i = 0; i < n; ++i) {
        int need = target - nums[i];
        auto it = hash_table.find(need);
        if (it != hash_table.end()) {
            return {it->second, i};
        }
        hash_table[nums[i]] = i;
    }
    return {};
}

易错点

• 题目要求返回的是数组下标，而不是两个元素的值。
• 暴力法的内层循环要从 i + 1 开始，不能从 i 开始。
• 哈希表中查找的是补数 target - nums[i]，不是当前元素 nums[i]。
• 哈希表法要先查找再插入，以正确处理 [3, 3] 这类输入。
• 如果对数组进行排序，原始下标会发生变化，需要额外保存下标信息。

总结

暴力法直接枚举所有组合，思路简单，但时间复杂度为 $O(n^2)$。哈希表法把“寻找另一个数”转化为“判断补数是否出现过”，使用 $O(n)$ 的额外空间将平均时间复杂度优化到 $O(n)$。这也是本题最重要的解题思路。

相关题目

• 167. 两数之和 II - 输入有序数组
• 15. 三数之和
• 18. 四数之和
• 454. 四数相加 II