1. Two Sum


Given an array of integers, returnindicesof the two numbers such that they add up to a specific target.

You may assume that each input would haveexactlyone solution.

Example:

Givennums=[2,7,11,15],target=9,Becausenums[0]+nums[1]=2+7=9,return[0,1].

题目大意：

在一个数组中找出2个元素的和等于目标数，输出这两个元素的下标。

思路：

最笨的办法喽，双循环来处理。时间复杂度O(n*n)。

代码如下：

classSolution{public:vector<int>twoSum(vector<int>&nums,inttarget){vector<int>result;inti,j;for(i=0;i<nums.size();i++){for(j=i+1;j<nums.size();j++){if(nums[i]+nums[j]==target){result.push_back(i);result.push_back(j);break;}}}returnresult;}};

参考他人的做法：https://discuss.leetcode.com/topic/3294/accepted-c-o-n-solution

采用map的键值，把元素做键，把元素的下标做值。

vector<int>twoSum(vector<int>&numbers,inttarget){//Keyisthenumberandvalueisitsindexinthevector.unordered_map<int,int>hash;vector<int>result;for(inti=0;i<numbers.size();i++){intnumberToFind=target-numbers[i];//ifnumberToFindisfoundinmap,returnthemif(hash.find(numberToFind)!=hash.end()){result.push_back(hash[numberToFind]);result.push_back(i);returnresult;}//numberwasnotfound.Putitinthemap.hash[numbers[i]]=i;}returnresult;}

2016-08-11 15:02:14