leetcode productExceptSelf题解

今天本来想刷一题leetcode用来给愉快的周末总结一下，所以我就随机愉快的挑了一题，
但是没有想到 这道题对我这只弱鸡很久都没解出来 还是看了别人的算法之后，思考了很久，话不多说
先放题目
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
其实这道题目很简单 如果使用遍历的方法，但难就难在题目要求 Note: Please solve it without division and in O(n).
好吧 于是我看到了别人的题解，先放上代码好了

  /**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function (nums) {
    var len = nums.length;
    if (len < 1)
        return;
    var result = [];
    // 存储前面几位的数值
    var productSoFar = 1;
    for (var i = 0; i < len; i++) {
        result[i] = productSoFar;
        productSoFar = nums[i] * productSoFar;
    }
    // console.log('result', result)
    productSoFar = 1;
    for (var j = len - 1; j >= 0; j--) {
        result[j] *= productSoFar;
        productSoFar *= nums[j];
    }
    return result;
};

这个算法用了一个很巧妙的步骤，主要分为两部分，
第一步 先用数组存储 自己前面项的乘积

  var productSoFar = 1;
  for (var i = 0; i < len; i++) {
      result[i] = productSoFar;
      productSoFar = nums[i] * productSoFar;
  }
// 这一步result[i]存储的是从第一项一直到num[i - 1]的乘积

当存储完前面项的乘积后，重新将productSoFar这个中间变量设置为1 然后让他从后往前存储
由于在第一步里 result数组的最后一项 存储的一定是所给nums数组最后一项之前所有项的乘积，所以先从result后遍历，也就是这一步

productSoFar = 1;
for (var j = len - 1; j >= 0; j--) {
    result[j] *= productSoFar;
    productSoFar *= nums[j];
}

然后就是让之前存储前项乘积的结果 乘上 nums[i]后面的项，这个算法的时间复杂度 是两个O(n)遍历的相加 因此也在范围内