[LeetCode]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

先贴上第一次submit的代码:

	int find(vector<int>& numbers,int begin,int x){
		for (int i = begin; i < numbers.size(); i++){
			if (numbers[i] == x)
				return i;
		}
		return -1;
	}
	vector<int> twoSum(vector<int> &numbers, int target) {
		vector<int> index;
		queue<int> q;
		int i = 0;
		for (; i < numbers.size(); i++){
			q.push(i + 1);
			int temp = target - numbers[i];
			int index2 = find(numbers, i + 1, temp);
			if (index2 == -1){
				q.pop();
			}
			else{
				q.push(index2 + 1);
				break;
			}
		}
		if (q.size() == 2){
			index.push_back(q.front());
			q.pop();
			index.push_back(q.front());
		}
		return index;
	}

问题在于，在查找target-numbers[i]的时候，是顺序查找的==。索性直接用现有容器了，再贴上修改后AC的代码：

class Solution {
public:

   vector<int> twoSum(vector<int> &numbers, int target){
		unordered_map<int, int> index;
		vector<int> result;
		for (int i = 0; i < numbers.size(); i++){
			if (!index.count(target - numbers[i])){
				index[numbers[i]] = i;
			}
			else{
				result.push_back(index[target - numbers[i]] + 1);
				result.push_back(i + 1);
			}
		}
		return result;
	}
};

[LeetCode]Two Sum

原文：http://blog.csdn.net/kaitankedemao/article/details/43340407