消息关闭
    暂无新消息!

就是关于这个算法的代码,用javascript实现的,但是下面这个算法没看懂。求大神解释。

var twoSum = function(nums, target) {
    var ret = [];
    var exist = {};
    for(var i = 0; i < nums.length; i++){
        if(typeof(exist[target - nums[i]]) !== 'undefined'){
            ret.push(exist[target - nums[i]]);
            ret.push(i + 1);
        }
        
        exist[nums[i]] = i + 1;
    }
    
    return ret
};

2个回答

︿ 3

题主可以试着用例子代入进去走读一遍代码。下面是我的见解:

比如就按截图里的例子:

for循环里主要是遍历第一个参数数组,然后它做的关键两个步骤:

我们先看if后面那个, exist[nums[i]] = i + 1; 这句是每个循环都会执行的,exist在这里是字典的意思,比如遍历第一个数是2(i=0),于是exist就保存了:{2:1} 这样的键值对,所以一遍循环下来,exist将会是:
数组反过来,“元素值”:"数组索引+1"的键值对字典。

接下来,再去看if里面的判断,当然for循环i=0时,exist还没有注入键值对,if表达式为false

但到了i=1的时候 exist[target-nums[1]] 即exist[9-7] = exist[2], 这不就是刚才i=0的时候,就注入exist的第一个键值对么?于是乎,把对应的键值对的值(其实就是原数值的在原来数组的索引+1)存档ret去,接着又把当前的 i+1 也存到ret……最后循环走完,返回ret,于是得到了[1,2] ps:题主给的例子答案跟代码的不一致。

总结:这个算法核心就是利用的对象exist来存已遍历过的数组元素,利用target-nums[i] 反过来间接通过exist来查找数组已遍历过的元素是否存在符合条件的元素。

︿ 2

这个原理是用字典做缓存查询,以减小时间复杂度(以空间换时间)。

原理的具体细节是这样的:

使用一个名为exists的字典,对于数组里的某个数n, 计算出 m = sum - n;

  1. 如果字典exists中存在键为m的对,则取出 m 对应的索引,和 n 的索引一起保存起来,这一组之和就是sum,n + m = n + (sum -n) = sum。

  2. 如果不存在,就将n和它的索引存入字典。

这样的好处是,只需要循环一次,时间复杂度是O(n)。