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].
解題思路
時間復(fù)雜度：O(n)
1、用一個map保存已遍歷的value到index的映射大溜。
2聚至、遍歷數(shù)組蕾羊，用target與當(dāng)前value的差值查找map，如果存在則可以直接返回結(jié)果褂乍。
3涎永、不存在，則將當(dāng)前value到index的映射存儲到map中供后續(xù)遍歷使用诉濒。
4、利用map就不必對于每個value都重新遍歷一次數(shù)組查找對應(yīng)的差值夕春。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;
}
};
