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].
#include <map>
#include <iterator>
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> m;
vector<int> v(2);
map<int, int>::iterator iter;
for(int i = 0; i < nums.size(); ++i){
iter = m.find(target - nums[i]);
if(iter != m.end()){
v[0] = iter->second, v[1] = i;
break;
}
m[nums[i]] = i;
}
return v;
}
};
Runtime: 12 ms, faster than 93.28% of C++ online submissions for Two Sum.
Memory Usage: 10.1 MB, less than 54.10% of C++ online submissions for Two Sum.
思路
- 遍歷數(shù)組足画，插入<value, index>之前查找是否存在key=value（避免出現(xiàn)重復(fù)的key）
- 存在則return [index, i], 不存在繼續(xù)遍歷
