两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

来源：力扣（LeetCode）
链接：https:///problems/two-sum

首先我没考虑暴力破解，去想优良的解法，但一直找不到，后来试了一下暴力破解，其实暴力破解就是这答案的一种。
之所以记录这个简单的题是因为我没想到哈希，数据结构学了哈希却一直没用过，所以记录下这个题。

1.暴力破解

这个就不解释了，直接上代码。

1 vector<int> twoSum(vector<int>& nums, int target) {
2 for(int i = 0; i < nums.size() - 1; i++)
3 for(int j = i + 1; j < nums.size(); j++)
4 if(nums[i] + nums[j] == target)
5 return {i,j};
6 return {};
7 }

View Code

2.哈希

 

 1 class Solution {
 2 public:
 3 vector<int> twoSum(vector<int>& nums, int target) {
 4 unordered_map<int, int> hashtable;
 5 for (int i = 0; i < nums.size(); ++i) {
 6 auto it = hashtable.find(target - nums[i]);
 7 if (it != hashtable.end()) {
 8 return {it->second, i};
 9 }
10 hashtable[nums[i]] = i;
11 }
12 return {};
13 }
14 };

View Code

 

来源于https:///problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/