两数之和：从暴力到哈希表

问题描述

给定一个整数数组nums和一个整数目标值target，在数组中找出和为目标值的两个整数，并返回它们的数组下标。题目保证只有一个有效答案，且不能使用两次相同的元素。

解题思路

1. 暴力解法：双重循环

• 核心思想：遍历数组中的每个元素，再遍历其后的所有元素，检查两数之和是否等于target。
• 时间复杂度：O(n²)（n为数组长度，最坏情况下需遍历n*(n-1)/2次）。
• 空间复杂度：O(1)（无需额外空间）。
• 示例代码：

vector<int> twoSum(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 {}; // 题目保证有解，实际不会执行 }

2. 哈希表优化：空间换时间

• 核心思想：使用哈希表（unordered_map）存储已遍历元素的值和下标，遍历数组时，计算当前元素与target的差值complement，若complement存在于哈希表中，则直接返回两个下标；否则将当前元素存入哈希表。
• 时间复杂度：O(n)（仅需遍历一次数组，哈希表查询时间为O(1)）。
• 空间复杂度：O(n)（最坏情况下需存储n-1个元素）。
• 示例代码：

#include <unordered_map>

#include <vector>

using namespace std;

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

unordered_map<int, int> numMap; / /key: 元素值，value: 下标

for (int i = 0; i < nums.size(); ++i) {

int complement = target - nums[i];

if (numMap.find(complement) != numMap.end()) {

return {numMap[complement], i}; // 返回已存下标和当前下标

}

numMap[nums[i]] = i; // 存入当前元素

}

return {}; // 题目保证有解，实际不会执行 }

}；

方法对比

注意事项

1. 元素唯一性：题目要求“不能使用两次相同的元素”，因此哈希表存储的是已遍历元素，避免重复使用当前元素（如示例3中的[3,3]，第一个3存入哈希表后，第二个3计算complement=3时，直接返回两个下标）。
2. 返回顺序：哈希表中存储的是已遍历元素的下标，因此返回时需先返回哈希表中的下标（如示例2中的[3,2,4]，遍历到2时，complement=4不存在，存入2→1；遍历到4时，complement=2存在，返回[1,2]）。

总结

两数之和问题的最优解是哈希表优化法，通过空间换时间将时间复杂度从O(n²)降至O(n)，适用于大多数场景。暴力解法虽然简单，但效率较低，仅适用于小规模数据。在实际开发中，应优先选择哈希表优化法，以提升程序性能。