Leetcode No.1 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.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

方法一：

使用哈希表，时间复杂度O(n)，空间复杂度O(n)。遍历数组，对numbers[i]，在哈希表中寻找是否有target-numbers[i]，如果有则返回结果，没有则将<numbers[i], i+1>添加进哈希表。也就是说当最后找到这一对数字时，是找到了在numbers[i]之前添加进哈希表的对应项，所以返回时的顺序依次是：hash[target-numbers[i]], i+1。

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        vector<int> result;
        unordered_map<int, int> hash;
        for(int i=0;i!=numbers.size();i++){
            int findNumber=target-numbers[i];
            if(hash.find(findNumber)!=hash.end()){
                result.push_back(hash[findNumber]);
                result.push_back(i+1);
                return result;
            }else
                hash[numbers[i]]=i+1;
        }
    }
};

方法二：

先对数组排序，然后使用两个分别指向头尾的指针m, n遍历数组，如果numbers[m]+numbers[n]<target, m++; numbers[m]+numbers[n]>target, n--;否则返回结果。不过因为数组未排序，排序至少要O(nlgn)复杂度，还要另外记下数组元素原来的下标，不如使用哈希表方便。