leetcode-1.Two Sum(总结)

给定一个整型的array，同时给你一个值(target)，让你在这个数组中找到想加之和为target的两个数的下标，并返回；

get：

(1)利用哈希优化，空间换时间。

class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> twoSum; for(int i=0;i<nums.size();i++){ for(int j=i+1;j<nums.size();j++){ if((nums[i]+nums[j])==target){ twoSum.push_back(i); twoSum.push_back(j); } } } return twoSum; }

这种方法复杂度为O(n^2);当然不会让我用这么low的方法做；

直接用map加上hash映射；用数组中的数值做map的键，用数值对应的下标做map的值。这样做的好处就是优化了查找的时间。

vector<int> twoSum(vector<int>& nums, int target) { vector<int> twoSum; map<int, int> tmpmap;//键值为nums的值，变量值为nums下标 for (int i = 0; i < nums.size(); i++) { tmpmap[nums[i]] = i; } for (int i = 0; i < nums.size(); i++) { if (tmpmap.count(target - nums[i]) != 0 && tmpmap[target-nums[i]]!=i) {// 如果目标值减去循环到的值对应的下标不为0，或者不为i，【存在有另一个数与循环值相加等于target，则返回结果】 twoSum.push_back(i); twoSum.push_back(tmpmap[target - nums[i]]); break; } } return twoSum; }  

这样target-nums[i]会的到两个数中的另一个值t(target-nums[i])（nums[i]是两个中的一个），再检查map中是否含有这个数。那么还有一个坑就是不能自己加自己等于target。然后，找到合适的值时，先把i放进结果数组中，再把t对应的map的值放进去就OK了(map的值就是索引)。

还没结束！

还能优化一下

vector<int> twoSum(vector<int>& nums, int target) {       vector<int> twoSum;       map<int, int> tmpmap;//键值为nums的值，变量值为nums下标          for (int i = 0; i < nums.size(); ++i) {           if (tmpmap.count(nums[i]) != 0) {               twoSum.push_back(tmpmap[nums[i]]);               twoSum.push_back(i);               break;           }           tmpmap[target - nums[i]] = i;       }       return twoSum;   }  

这个真的太巧妙了；看完大佬的博客。感慨

从第一个数开始往map中放，仍然是map的键是数值。map的值是下标；

放的时候并不是把这个数直接放进去，而是把tartget-nums[i]放进去。也就是把和当前和这个数相加后等于target的那个数放进去。然后在后面如果碰到了那么说明找到了。直接再把target-nums[i]对应的map的值放入结果数组，再把nums[i]对应的索引放进结果数组就完成了。