当前位置：首页 > news >正文

力扣刷题#1：两数之和_从暴力解法到哈希表优化

news 2026/6/2 22:39:01

两数之和：从暴力解法到哈希表优化

题目描述

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。

示例：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9，返回 [0, 1]。

思路一：暴力枚举（O(n²)）

最直观的方法是两层循环枚举所有数对，检查它们的和是否等于 target。

第一次尝试（有 bug）

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();for(int i = 0; i < n-1; i++){for(int j = i+1; j < n; i++)   // 错误：这里是 i++{if(nums[i] + nums[j] == target){return {i, j};}}}return {};}
};

运行后出现 heap-buffer-overflow 错误，因为内层循环误将 i++ 写成了 j++，导致 i 在内层循环中不断自增，很快超出数组范围，访问非法内存。

修正后的暴力解法

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();for(int i = 0; i < n-1; i++){for(int j = i+1; j < n; j++)   // 正确：j++{if(nums[i] + nums[j] == target){return {i, j};}}}return {};}
};

复杂度	值
时间复杂度	O(n²)
空间复杂度	O(1)

提示：直接写 i < nums.size()-1 会有风险，因为 nums.size() 返回 size_t（无符号整数），当数组为空时 size()-1 会下溢成一个极大值，导致循环条件永远为真。推荐先用 int n = nums.size(); 保存长度。

思路二：哈希表（O(n)）

暴力解法虽然简单，但面试官通常会要求更优解。我们可以利用哈希表将查找 target - x 的时间从 O(n) 降到 O(1)。

核心思想

遍历数组，对于每个元素 nums[i]，计算 complement = target - nums[i]。

在哈希表中查找 complement：
- 如果存在，说明之前已经遍历过这个补数，直接返回两个下标。
- 如果不存在，将 (nums[i], i) 存入哈希表，继续向后遍历。

常见错误：将迭代器赋值给 int

初学者的一个典型错误是：

int it = hash.find(target - nums[i]);   // 错误！

unordered_map::find() 返回的是迭代器，不是整数。迭代器可以理解为指向 pair<const Key, Value> 的指针，不能直接赋给 int。

正确的做法是用 auto 接收迭代器，然后判断是否等于 hash.end()：

auto it = hash.find(complement);
if (it != hash.end()) {return {it->second, i};
}

正确实现

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash;   // 值 -> 下标int n = nums.size();for (int i = 0; i < n; i++) {int complement = target - nums[i];auto it = hash.find(complement);if (it != hash.end()) {return {it->second, i};   // it->second 是先前元素的下标}hash[nums[i]] = i;            // 将当前元素加入哈希表}return {};}
};