leetcode上看到的题,意思是说在一个数组里如何找到两个数之和为指定数字的两个下标,例如:[2,7,3,1],和为9的两个数字下标为[0,1](也就是2+7=9),这里假设在数组中这样的组合只存在一个,请问如何找出这一组数据。

看到题的第一眼思路就是两个for,这样的思路应该非常普通,实现起来大致如下:

var twoSum = function(nums, target) {
    var judge=true,_i,_j;
    for(var i=0;i<nums.length;i++){
        for(var j=i+1;j<nums.length;j++){
            if(nums[i]+nums[j]==target){
                _i=i;
                _j=j;
                judge=false;
                break;    
            }
        }
        if(!judge){
            break;
        }
    }
    return [_i,_j];
};

不过看到别人的答案,觉得很巧妙,它是利用一个map只遍历一遍就找到正确了,利用的是一种逆向思维,例如[2,7,3,1],目标和为9,那么我们知道目标和当前的数字,我们就可以知道另外一半的数字,如当前数字为2,9-2=7,我们就知道另外一半的数字肯定为7,我们把7放入临时的map中,判断以后数字是否有7的(在map中找,因为7是key,因此很快),如果找到就搜索结束了。

var twoSum = function(nums, target) {
    var hash = {};
    var len = nums.length;
    for (var i = 0; i < len; i++) {
        if (nums[i] in hash) return [hash[nums[i]], i];
        hash[target - nums[i]] = i
    }
    return [-1, -1];
};
回到顶部
我要评论

所有评论

返回
邮箱:
绑定
取消
×

我要评论

回复:

昵称:(昵称不超过20个字)

图片:

邮箱:
绑定邮箱后,若有回复,会邮件通知。
提交
还可以输入500个字