Two Sum

作者 iHugo 日期 2016-11-17
Two Sum

给定一组数和一个目标值,求出两个加数的位置。

比如:

nums = [2, 7, 11, 15], target = 9
因为nums[0] + nums[1] = 2 + 7 = 9,
返回 [0, 1]

注意返回的位置是基于0的

##方法一 O(n^2)

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
for (var i=0; i<nums.length; i++) {
for (var j=i+1; j<nums.length; j++) {
if ((nums[i] + nums[j]) == target) {
return [i, j];
}
}
}
};

##方法二 O(n)

/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
let map = new Map();
for (var i=0; i<nums.length; i++) {
let nextNum = target - nums[i]
if (map[nextNum] !== undefined) {
let result = []
result.push(map[nextNum])
result.push(i)
return result
}
map[nums[i]] = i
}
};

##总结
方法二巧妙利用hashMap取值的时间是固定的这一特点。把复杂度从O(n^2) 降到了O(n)。