两数之和原题地址

方法一：暴力枚举

首先，我们需要枚举数组中所有可能的下标对组合，对于n个数的数组，从中选2个下标，有种可能。做法很简单，遍历数组中的所有元素，对于每一个元素，遍历该元素后面的所有元素即可。

比如，对于4个元素的数组，下标是0~3，所有可能的组合就是：(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)，总共有种可能。

// 方法一：暴力枚举
class Solution {
public: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){// 判断下标对(i,j)是否满足条件if (nums[i] + nums[j] == target){return { i, j };}}}// 不存在满足条件的下标对return {};}
};

方法二：哈希表

暴力枚举的方法时间效率太低了，最坏的情况要把任意两个数都匹配一次。我们可以考虑把数组中的元素都存储到哈希表中，遍历数组中的元素，查找哈希表中是否有元素和数组中的元素匹配。

再具体一点，对于数组中的某一个元素，如果哈希表中有与之匹配的元素，就找到了符合题目要求的答案；如果没有元素与之匹配，就把这个元素存储在哈希表中。这样的话，对于数组中的每一个元素，只需要O(1)的时间复杂度就能匹配完，效率大大提升了。

C++中，需要使用unordered_map，而不是unordered_set，因为最终要返回的是数组的下标，所以要把数组的元素和对应的下标都存储到哈希表中。

// 方法二：哈希表
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {// 由于要返回下标，所以下标和元素都要存储unordered_map<int, int> hashtable;int n = nums.size();for (int i = 0; i < n; ++i){// 对于每个元素，查找哈希表中是否存在匹配的元素auto it = hashtable.find(target - nums[i]);if (it != hashtable.end()){// 找到了return { i, it->second };}// 插入元素及下标hashtable[nums[i]] = i;}// 不存在满足条件的下标对return {};}
};