[Leetcode] 1.Two Sum（unordered

[Leetcode] 1.Two Sum（unordered_map）

1.首先想到的方法就是两个for循环全部遍历，代码如下，可通过，但效率太低

 1 class Solution
 2 {
 3 public:
 4     vector<int> twoSum(vector<int> nums, int target)
 5     {
 6         vector<int> res;
 7         for (int i = 0; i < nums.size(); i++)
 8         {
 9             for (int j = i + 1; j < nums.size(); j++)
10             {
11                 if (nums[j] == target - nums[i])
12                 {
13                     res.push_back(i);
14                     res.push_back(j);
15                 }
16             }
17         }
18         return res;
19     }
20 };

2.使用unordered_map,遍历vector中每个元素，并在hash表中通过find()查找目标元素，若找到则写入结果，否则将当前元素加入到hash表中。（每次调用find()函数是为了判断当前元素与其前面的元素之和是否为target值）。

 1 class Solution
 2 {
 3 public:
 4     vector<int> twoSum(vector<int> nums, int target)
 5     {
 6         unordered_map<int,int> hash;
 7         vector<int> res;
 8         for (int i = 0; i < nums.size(); i++)
 9         {
10             int numTofind = target - nums[i];
11             
12             if(hash.find(numTofind) != hash.end())
13             {
14                 res.push_back(hash[numTofind]);
15                 res.push_back(i);
16             }
17             else
18             {
19                 hash[nums[i]] = i;
20             }
21         }
22         return res;
23     }
24     
25 };