1.two sum

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;

}