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;
    }
};