描述 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:

Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

[Two Sum]

分析 Analysis

方法1

两重循环，速度很慢，O(N^2)

方法2：夹逼方法

先排序，然后左右夹逼，排序O(nlogn)，左右夹逼O(n){左边为i，右边为j，如果两数和>sum，则必然是右边数太大，所以j左移，否则是左边数太小，所以i右移}，最终O(nlogn)。但是注意，这题需要返回的是下标，而不是数字本身，所以要用一个数据结构存好键值对应关系，如hashmap。

Two Sum问题变型

在二叉查找树中查找和为某个定值的两个数。

相当于给了你一个有序数组，最小总是在左子树上，即从最左子树开始找其后继；最大的总是在右子树上，即从最右子树开始找其前驱。

方法3（lz推荐）

hash。用一个哈希表，存储每个数对应的下标，复杂度O(n)。

代码 Code

方法3

vector<int> twoSum(vector<int> &numbers, int target)
{
    //Key is the number and value is its index in the vector.
    unordered_map<int, int> hash;
    vector<int> result;
    for (int i = 0; i < numbers.size(); i++) {
        int numberToFind = target - numbers[i];

            //if numberToFind is found in map, return them
        if (hash.find(numberToFind) != hash.end()) {
                    //+1 because indices are NOT zero based
            result.push_back(hash[numberToFind]);
            result.push_back(i);            
            return result;
        }

            //number was not found. Put it in the map.
        hash[numbers[i]] = i;
    }
    return result;
}