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].
解题思路
时间复杂度：O(n)
1、用一个map保存已遍历的value到index的映射。
2、遍历数组，用target与当前value的差值查找map，如果存在则可以直接返回结果。
3、不存在，则将当前value到index的映射存储到map中供后续遍历使用。
4、利用map就不必对于每个value都重新遍历一次数组查找对应的差值。map的访问时间是O(1)的。
解题源码
#include<vector>
#include<iostream>
#include<map>
using namespace std;
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> value_index_map;
vector<int> res;
int len = nums.size();
for (int i = 0; i < len; ++i) {
int d = target - nums[i];
if (value_index_map.find(d) != value_index_map.end()) {
res.push_back(value_index_map[d]);
res.push_back(i);
return res;
}
else
{
value_index_map[nums[i]] = i;
}
}
return res;
}
};
