Leetcode 编程训练[1]:Two Sum

2015-03-23

2 min read

#1: 题目要求是接收两个参数，一个数组参数存放整型数据，另一个参数为整型变量。我们需要找到两个数组内的数字，相加为整型参数，并返回这两个数字的位置。并且，给出的参数有且只有一个符合要求的组合。

首先，我想到的方法就是来用两个循环来历遍数组。代码如下：

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]} two integers in an array, ie: [index1, index2]
 */
var twoSum = function(numbers, target) {
    var index1 = 0,
        index2 = 0;        
    //loop
    var length = numbers.length;
    for(var i = numbers.length; i--;){
        for(var j = i; j--;){
            if((numbers[i] >= numbers[j]) && (numbers[i] + numbers[j] == target)){
                index1 = i + 1;
                index2 = j + 1;
                break;
            }
        }        
    }        
    return [index1, index2];
};

满怀欣喜地提交代码，结果却是因为超时而未通过。原来这个方法的时间复杂度是O(n^2)，系统的要求要减少复杂的。在网上搜答案，我的这种解法就叫蛮力法。更好的方法是通过哈希表得到时间复杂度是O(n)的方法，不过这种方法使得空间复杂度提高到了O(n)。很有意思。

这要怎么做的呢？我们看到内层循环其实只是在搜索匹配符合要求的情况，在搜索时外层标记变量i到来记录第一个加数的位置。我们可以把外层的记录放在哈希表上，将两次循环功能合并起来。

为什么使用哈希表这种数据结构了，因为我们需要使用哈希表的键值映射的特点。哈希表反过来着将每个元素数字所缺的加数target-numbers[i]作为哈希表的键（Key），而将整型元素所在下标存为所对应的值（Value）。这样在查找时，将第二个数字作为表的键来寻找，如果没有定义则将其作为新元素存储在表中。知道找到组合。

在coding的时候，犯了几个错误。首先，不知道在JS语言中，哈希表要怎么实现。搜索结果知道JS中对象就可以充当哈希表用，也就是JSON数据。二是map对象中没有数据的key存放的是undefined而不是null。

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]} two integers in an array, ie: [index1, index2]
 */
var twoSum = function(numbers, target) { 
    //结果表    
    var result = [];    
    //映射表对象存储 key == number , value == position
    var map = {};
    //loop
    var length = numbers.length;
    for(var i = 0; i < length; i++){
        // 嵌套循环 o(n^2)复杂度 搜索
        // 需要使用映射表来减少收缩复杂度(o(n)->o(1))
        if(map[numbers[i]] === undefined){
            map[target- numbers[i]] = i;
        }else{
            result.push(map[numbers[i]] + 1);
            result.push(i + 1);
        }        
    }    
    return result;
};

最后运行的时间差不多160毫秒嘛，相比之下，c系果然是贴合性能王道。

Rescoure: 程序源码

Leetcode 编程训练[1]:Two Sum

See Also