题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，且同一个元素不能使用两次。

思路分析

这题最直接的方法是双重循环，时间复杂度是 O(n^2)。但题目本身非常适合用哈希表优化到 O(n)。

核心想法：

  1. 遍历数组当前元素 nums[i]。
  2. 计算它需要的配对值 need = target - nums[i]。
  3. 去哈希表里查找 need 是否已经出现过。
  4. 如果出现过，直接返回两个下标。
  5. 如果没出现，把当前值和当前下标存进哈希表，继续遍历。

因为哈希表查找平均是 O(1)，所以整体复杂度变成线性。

C++ 代码实现

class Solution {
public:
  vector<int> twoSum(vector<int> &nums, int target) {
    unordered_map<int, int> visited;

    for (int i = 0; i < nums.size(); ++i) {
      int need = target - nums[i];
      auto iter = visited.find(need);

      if (iter != visited.end()) {
        return {iter->second, i};
      }

      visited[nums[i]] = i;
    }

    return {};
  }
};

复杂度分析

  • 时间复杂度：O(n)，每个元素最多遍历一次，哈希查找平均 O(1)。
  • 空间复杂度：O(n)，最坏情况下所有元素都要存入哈希表。

哈希表知识点（对应你的 4 个问题）

1. 为什么要使用哈希表？

因为这题需要频繁判断“某个值是否出现过”。哈希表的查找速度快（平均 O(1)），可以把暴力解法的 O(n^2) 降到 O(n)。

2. 为什么这里要用 unordered_map？

unordered_map 是哈希表实现，不要求有序，查找和插入平均更快，正适合本题。

补充：

  • map：红黑树，有序，查找/插入是 O(log n)。
  • unordered_map：哈希表，无序，查找/插入平均 O(1)。
  • multimap：红黑树，可重复键，一般不用于这题。

3. 在这道题里，map 的作用是什么？

作用是“记录历史元素”，并且支持快速反查：

  • 当前遍历到 nums[i] 时，快速判断 target - nums[i] 之前有没有出现过。

4. map 里的 key 和 value 存的是什么？

  • key：数组元素值（nums[i]）
  • value：该元素对应的下标（i）

这样找到配对值时，就能立即拿到它的下标并返回答案。