leetCode之two sum

Two Sum

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.

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

解法一

var twoSum = function(nums, target) {
        for(let i=0,len = nums.length;i<len;i++){
            for(let j=i+1;j<len;j++){
                if(nums[i]+nums[j]===target){
                    return [i,j]
                }
            }
        }
    };

上面的解法需要两个循环，时间复杂度高

解法二

var twoSum = function(nums, target) {
    var len = nums.length;
    var hash = {};
    var i = 0;
    do {
        var a = nums[i];
        var j = hash[a];
        if (j !== undefined) {
            return [j, i ];
        } else {
            hash[target - a] = i;
        }
    } while (++i < len);
};

利用hash表