下面的这段算法代码求解释

Question

就是关于这个算法的代码，用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
};

Answer 1

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

比如就按截图里的例子：

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来查找数组已遍历过的元素是否存在符合条件的元素。

Answer 2

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

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

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

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

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

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