Two Sum

发表于 更新于

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

比如：

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

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

##方法一 O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * @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)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @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)。