leetcode 面试经典 150 题：两数之和

链接	两数之和
题序号	1
题型	数组
解题方法	1. 哈希表，2. 暴力法
难度	简单
熟练度	✅✅✅✅✅

题目

• 给定一个整数数组 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⁹
  只会存在一个有效答案

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

题解

1. 核心思想：

   • 使用一个哈希表来存储数组元素及其对应的下标。键是数组元素，值是元素的下标。
   • 遍历数组，对于每个元素 nums[i]，计算 complement = target - nums[i]。
   • 检查 complement 是否在哈希表中。如果在，说明找到了两个数，它们的和为 target，直接返回它们的下标；如果不在，将当前元素 nums[i] 及其下标 i 存入哈希表。

2. 复杂度：时间复杂度O(N)，空间复杂度O(N)。

3. c++ 实现算法：

vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> numMap; // 用于存储数字和它的索引//遍历数组 nums，从索引 i = 0 开始，直到数组的最后一个元素for (int i = 0; i < nums.size(); ++i) {int complement = target - nums[i]; // 计算当前数字需要的补数//检查哈希表中是否存在补数 complement。如果找到了，表示我们已经找到了一对数字，//它们的和为 target。find 函数用于查找哈希表中是否存在给定的键（complement）。//如果存在，find 会返回一个指向该元素的迭代器，否则返回 end()。if (numMap.find(complement) != numMap.end()) {return {numMap[complement], i}; // 返回补数的索引和当前数字的索引，找到了就直接返回不需要继续找了}//它的键是数组中的元素，值是该元素的索引。//通过 numMap[nums[i]] = i，我们将当前元素 nums[i] 的值作为键，将其索引 i 作为值存储在哈希表中。numMap[nums[i]] = i; }return {}; // 如果没有找到符合条件的结果，返回空数组
}

4. 算法推演：

• 假设输入数组 nums = [2, 7, 11, 15] 和目标值 target = 9。

• 步骤 1：初始化哈希表
  unordered_map<int, int> numMap; 这里创建了一个哈希表 numMap，它的键（key）是数组中的元素，值（value）是该元素的索引。哈希表的作用是快速查找数组中是否已经存在与当前数字相加等于目标值的数字。

• 步骤 2：遍历数组
  我们开始遍历数组 nums。

  • 第一次迭代（i = 0，nums[i] = 2）：
    计算补数：complement = target - nums[0] = 9 - 2 =7。
    检查哈希表中是否有 complement = 7： numMap.find(7) 返回 numMap.end()，表示没有找到补数。
    将 nums[0] = 2 和它的索引 0 存入哈希表：numMap[2] = 0。
    当前哈希表状态：numMap = {2: 0}。
  • 第二次迭代（i = 1，nums[i] = 7）：
    计算补数：complement = target - nums[1] = 9 - 7 = 2。
    检查哈希表中是否有 complement = 2： numMap.find(2) 返回 numMap[2] = 0，表示找到了补数
    2，它的索引是 0。
    找到符合条件的两个数字：nums[0] = 2 和 nums[1] = 7，它们的和是 9。
    返回这两个索引：return {numMap[2], 1}，即返回 [0, 1]。

5. c++ 完整 demo：

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> numMap; // 用于存储数字和它的索引//遍历数组 nums，从索引 i = 0 开始，直到数组的最后一个元素for (int i = 0; i < nums.size(); ++i) {int complement = target - nums[i]; // 计算当前数字需要的补数//检查哈希表中是否存在补数 complement。如果找到了，表示我们已经找到了一对数字，//它们的和为 target。find 函数用于查找哈希表中是否存在给定的键（complement）。//如果存在，find 会返回一个指向该元素的迭代器，否则返回 end()。if (numMap.find(complement) != numMap.end()) {return {numMap[complement], i}; // 返回补数的索引和当前数字的索引，找到了就直接返回不需要继续找了}//它的键是数组中的元素，值是该元素的索引。//通过 numMap[nums[i]] = i，我们将当前元素 nums[i] 的值作为键，将其索引 i 作为值存储在哈希表中。numMap[nums[i]] = i; }return {}; // 如果没有找到符合条件的结果，返回空数组
}int main() {vector<int> nums = {2, 7, 11, 15};int target = 9;vector<int> result = twoSum(nums, target);if (!result.empty()) {cout << "Indices: " << result[0] << ", " << result[1] << endl;} else {cout << "No solution found!" << endl;}return 0;
}