【力扣】两数之和，暴力枚举 + 哈希表

两���之和原题地址

方法一：暴力枚举

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

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

0 1 2 3^ ^^   ^^     ^  ^ ^  ^   ^    ^ ^

// 方法一：暴力枚举class Solution{public:    vector twoSum(vector& nums, int target)    {        // 暴力枚举        for (int i = 0; i  
方法二：哈希表
 
暴力枚举的方法时间效率太低了，最坏的情况要把任意两个数都匹配一次。我们可以考虑把数组中的元素都存储到哈希表中，遍历数组中的元素，查找哈希表中是否有元素和数组中的元素匹配。
 
再具体一点，对于数组中的某一个元素，如果哈希表中有与之匹配的元素，就找到了符合题目要求的答案；如果没有元素与之匹配，就把这个元素存储在哈希表中。这样的话，对于数组中的每一个元素，只需要 O(1) 的时间复杂度就能匹配完，效率大大提升了。
 
C++ 中，需要使用 unordered_map ，而不是 unordered_set ，因为最终要返回的是数组的下标，所以要把数组的元素和对应的下标都存储到哈希表中。
 
// 方法二：哈希表class Solution{public:    vector twoSum(vector& nums, int target)    {        unordered_map um;        for (int i = 0; i second };            }            // 存入哈希表            um[nums[i]] = i;        }        return {};    }};