Two-Sum

问题：
Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2



思路：

（1）使用数据结构map

（2）不着急把所有数据放到map中去，首先查找target-numbers[i]值在不在map中，在说明找到了，第一个index是找到的map中保存的index，第二个index是当前的i;

（3）如果target-numbers[i]值没找到，并且当前的numbers[i]不在map中，将当前值加入map中。

代码：

class Solution {
public:
  vector<int> twoSum(vector<int> &numbers, int target) {
    vector<int> index;
    map<int, int> mp;

    map<int, int>::iterator iter;
    for(int i = 0; i != numbers.size(); ++i) {
      iter = mp.find(target-numbers[i]);
      if(iter != mp.end() ) {
	int start = mp.find(target-numbers[i])->second;
	int end = i + 1;
	index.push_back(start);
	index.push_back(end);
	return index;
      } else {
	map<int, int>::iterator it = mp.find(numbers[i]);
	if(it == mp.end()) {
	  mp[numbers[i]] = i + 1;
	}
      }
    }
  }
};