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)。


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 jaytp@qq.com

文章标题:Two Sum

字数:218

本文作者:ihugo

发布时间:2016-11-17, 10:01:45

最后更新:2022-03-11, 02:46:44

原始链接:http://ihugo.cc/2016/11/17/1-Two-Sum/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。