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

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

    1. var twoSum = function(nums, target) {
    2.     var judge=true,_i,_j;
    3.     for(var i=0;i<nums.length;i++){
    4.         for(var j=i+1;j<nums.length;j++){
    5.             if(nums[i]+nums[j]==target){
    6.                 _i=i;
    7.                 _j=j;
    8.                 judge=false;
    9.                 break;    
    10.             }
    11.         }
    12.         if(!judge){
    13.             break;
    14.         }
    15.     }
    16.     return [_i,_j];
    17. };

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

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

    所有评论

      相关文章