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.
这题思路是想到了，用target-numbers[i],得到的结果在numbers中查找，程序在vs也得到了正确的结果，
code 1
class Solution { public: vector<int> twoSum(vector<int> &numbers, int target) { int iTarPosFront = 0; int iTarPosTail = 0; int iPosCountFront = 0; int iPosCountTail = 0; vector<int> iPosVec; for(vector<int>::iterator iIter = numbers.begin(); iIter != numbers.end(); ++iIter) { ++ iPosCountFront; int iTailElem = target - *iIter ; for(vector<int>::iterator serIter = numbers.begin(); serIter != numbers.end(); ++serIter) { ++ iPosCountTail; if(iPosCountTail == iPosCountFront) { continue; } if(iTailElem == *serIter) { iTarPosFront = iPosCountFront; iPosVec.push_back(iTarPosFront); iTarPosTail = iPosCountTail; iPosVec.push_back(iTarPosTail); break; } } iPosCountTail = 0; if(!iPosVec.empty()) { break; } } return iPosVec; } };
这应该就是所说的冒泡法，时间复杂度是o(n^2),leetCode不干！自己确实太渣了，查找还停留在o(n^2)复杂度上，惭愧。网上找到使用stl的关联容器实现的，我的代码如下
class Solution { public: vector<int> twoSum(vector<int> &numbers, int target) { map<int, int> hMap; vector<int> iPos; for(int i = 0; i != numbers.size(); ++i) { if(!hMap.count(numbers[i])) { hMap.insert(pair<int, int>(numbers[i], i)); } if(hMap.count(target - numbers[i])) { int n = hMap[target - numbers[i]]; if(n < i) { iPos.push_back(n+1); iPos.push_back(i+1); return iPos; } } } return iPos; } };
学习c++的stl真心就会用一个string还有一个vector，惭愧，好好学习吧。
原文：http://www.cnblogs.com/bestwangjie/p/4340234.html