Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0,1].
关键点：
1.使用暴力搜索时间复杂度为O(n^2)，使用map搜索为O(n)；
2.map中的索引应为数组中的元素，map中的值应为数组的下标：numsMap[nums[i]]=i，这样方便使用numsMap.count(e)或numsMap.find(e)函数快速查找map中是否存在值e；
3.若数组中存在相同的元素（如nums=[2,2,3] target=4），若使用两次数组遍历会存在相同值相加的问题，如nums[0]+nums[0]=target。而在存入map时，而在遍历数组时，nums[0]=2,而numsMap中已经不存在<2,0>（<2,0>已被<2,1>覆盖），完美地解决了问题。
4.对于那些有顺序要求的问题，用map会更高效一些；对于查找问题，unordered_map会更加高效一些。
代码：
#include <iostream>
#include<vector>
#include <map>
using namespace std;
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
int remain;
map<int,int> numsMap;
for(int i=0;i<nums.size();i++)
{
// numsMap.insert(pair(nums[i],i));
numsMap[nums[i]]=i;
}
map<int,int>::iterator finder =numsMap.begin();
for(int j=0;j<nums.size();j++)
{
remain=target-nums[j];
finder=numsMap.find(remain);
if(finder!=numsMap.end() && j!=finder->second)
{
res.push_back(j);
res.push_back(finder->second);
break;
}
}
return res;
}
int main(int argc, const char * argv[]) {
// insert code here...
int b,target;
vector<int> nums,res;
while(cin>>b)
{
nums.push_back(b);
if(cin.get()=='\n')
{
break;
}
}
cin>>target;
res=twoSum(nums, target);
cout<<res.size()<<endl;
cout<<res[0]<<" "<<res[1]<<endl;
for(vector<int>::iterator it=res.begin(); it!=res.end();it++)
{
cout<<*it<<endl;
}
cout << "Hello, World!\n";
return 0;
}
