Two Sum

题目：

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.

接口：

class Solution {
public:
    /*
     * @param numbers : An array of Integer
     * @param target : target = numbers[index1] + numbers[index2]
     * @return : [index1+1, index2+1] (index1 < index2)
     */
    vector<int> twoSum(vector<int> &nums, int target) {
        // write your code here

    }
};

分析：

题目要求O(n)space, O(nlogn)time。同时，最好可以做到O(n)space, O(n)time。创建一个hash，用target - nums[i]做key，用i做value，当在hash中找到任意key时，构建vector()，返回下标。

解答：

class Solution {
public:
    /*
     * @param numbers : An array of Integer
     * @param target : target = numbers[index1] + numbers[index2]
     * @return : [index1+1, index2+1] (index1 < index2)
     */
    vector<int> twoSum(vector<int> &nums, int target) {
        // write your code here
        if (nums.size() == 0) {
            return vector<int>();
        }
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++) {
            if (hash.find(nums[i]) != hash.end() ) {
                vector<int> res(2);
                res[0] = hash[nums[i] ] + 1;
                res[1] = i + 1;
                return res;
            } else {
                hash[target - nums[i] ] = i;
            }
        }
        return vector<int>();
    }
};