2 Sum

http://www.lintcode.com/en/problem/two-sum/

Disussion

1. 暴力法，$$O(n^2)$$
2. array是无序的，先排序，再夹逼，排序O(n log n)，左右夹逼O(n)，最终O(n log n).题目要求返回下标，不是数字，所以不行
3. hash

Solution

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
        unordered_map<int, int> map;
        vector<int> result;
        for(int i=0; i<nums.size(); i++) {
            map[nums[i]] = i;
        }
        for(int i=0; i<nums.size(); i++) {
            if(map.find(target-nums[i]) != map.end()) {
                result.push_back(i+1);
                result.push_back(map[target-nums[i]] + 1);
                break;
            }
        }
        return result;
    }
};