Description

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

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Interface

1
2
3
4
5
6
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
    }
};

Solution

一开始，我想到用 stl::map 来解决，数组元素值作为 map 的键，下标则是作为对应的值。将 target 减去当前元素值，看 map 中是否存在差值的键值，如果存在就说明找到了，不存在则将当前元素值和对应下标存入 map 中，以便后面的元素能对应。

但是，我发现如果出现目标是一个元素的两倍，那么输出的结果将是两次那个元素的下标。为了解决这个情况，我调整了一下语句的顺序，将对 map 赋值的语句放到查找后，这样就不会出现上面所说的问题了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// e.g
intput: [2 4 4 7 10], target = 8
output: [1 1]

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> reflect;
        vector<int> result;
        for (int i = 0; i < nums.size(); i++) {
            if (reflect.find(target - nums[i]) != reflect.end()) {
                result.push_back(reflect[target - nums[i]]);
                result.push_back(reflect[nums[i]]);
                return result;
            }
            reflect[nums[i]] = i;
        }
        return result;
    }
};