两数之和（哈希表解法，时间复杂度 O (n)）

大家好，今天分享 LeetCode 第一题 “两数之和” 的最优解法，用哈希表把时间复杂度从暴力法的 O (n²) 降到 O (n)~

题目描述

给定整数数组nums和目标值target，找出数组中和为 target 的两个整数，返回它们的下标。

• 假设每种输入对应唯一答案
• 不能使用同一个元素两次

暴力法的问题

最直观的思路是 “双重循环遍历所有组合”：

for (int i=0; i<nums.size(); i++) { for (int j=i+1; j<nums.size(); j++) { if (nums[i]+nums[j] == target) return {i,j}; } }

但双重循环的时间复杂度是O(n²)，当数组很大时效率很低。

哈希表优化思路

核心是用空间换时间：用哈希表存储 “元素值 → 下标” 的映射，遍历数组时直接查 “目标差值” 是否已在表中。

步骤：

1. 定义哈希表unordered_map<int, int>，key 存元素值，value 存对应下标；
2. 遍历数组的每个元素nums[i]：
   • 计算目标差值complement = target - nums[i]；
   • 若complement在哈希表中 → 直接返回{哈希表中complement的下标, i}；
   • 若不在 → 把当前元素nums[i]和下标i存入哈希表；
3. 题目保证有解，无需额外处理边界。

完整代码（C++）

#include <vector> #include <unordered_map> using namespace std; class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { // 哈希表：key=元素值，value=元素下标 unordered_map<int, int> hashMap; for (int i = 0; i < nums.size(); ++i) { int complement = target - nums[i]; // 若差值已存在于哈希表，直接返回结果 if (hashMap.find(complement) != hashMap.end()) { return {hashMap[complement], i}; } // 否则将当前元素存入哈希表 hashMap[nums[i]] = i; } // 题目保证有解，此处仅为语法兜底 return {}; } };

代码解释

• 哈希表的作用：把 “查找差值” 的操作从暴力法的 O (n) 降到 O (1)；
• 遍历顺序：边遍历边存哈希表，保证不会重复使用同一个元素（因为查的是 “之前遍历过的元素”）；
• 时间 / 空间复杂度：
  • 时间：O (n)（仅遍历一次数组）；
  • 空间：O (n)（哈希表最多存 n 个元素）。

测试用例验证

以示例 2nums = [3,2,4], target = 6为例：

1. i=0，nums [0]=3 → complement=3，哈希表为空 → 存 {3:0}；
2. i=1，nums [1]=2 → complement=4，哈希表无 4 → 存 {2:1}；
3. i=2，nums [2]=4 → complement=2，哈希表中存在 2（下标 1）→ 返回 {1,2}。