Problem
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].
Solution 1
vector<int> twoSum(vector<int>& nums, int target) {
size_t mLength = nums.size();
vector<int> mVec;
mVec.resize(2);
for (int i = 0; i < mLength - 1; i++){
for(int j = i + 1; j < mLength; j++){
if (nums[i] + nums[j] == target){
mVec[0] = i;
mVec[1] = j;
return mVec;
}
}//inside-for
}//for
}
Solution 2
std::vector<int> twoSum(std::vector<int>& nums, int target) {
std::map<int, int> mMap;
std::vector<int> result;
result.reserve(2);
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
//map.find return iterator
auto iter = mMap.find(complement);
if (iter != mMap.end()){
result.push_back(mMap[complement]);
result.push_back(i);
return result;
}
mMap.insert(std::pair<int, int>(nums[i], i));
}
}//twoSum
- Solution2是一种贪心策略，对数组进行迭代，且迭代过程通过Map辅助进行问题求解。
