238. 除自身以外数组的乘积 （前缀和）

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

---

示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

---

示例 2:
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

---

【思路】：前缀、后缀和。
每一个位置最后的结果 = 该位置的前缀和 * 该位置的后缀和。

详细分析参照Leetcode 官方题解。

---

【初步代码】：

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    var leftArr = new Array(nums.length);           //存放前缀积
    var rightArr = new Array(nums.length); 

    leftArr.fill(1);
    rightArr.fill(1);
    //前缀积处理
    for(let i = 1;i < nums.length;i++){
        leftArr[i] = nums[i - 1]*leftArr[i-1];
    }
    //后缀积处理
    for(let i = nums.length - 2;i >= 0;i--){
        rightArr[i] = nums[i + 1] * rightArr[i + 1]; 
    }
    var res = [];
    for(let i = 0;i < nums.length;i++){
        res.push(leftArr[i] * rightArr[i]);
    }
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

但是这个代码不满足题目要求的空间复杂度

---

【第一次改进】：
可以用res数组来代替leftArr数组。

var productExceptSelf = function(nums) {
    var res = new Array(nums.length);      
    var rightArr = new Array(nums.length); 

    res.fill(1);
    rightArr.fill(1);
    //前缀和处理
    for(let i = 1;i < nums.length;i++){
        res[i] = nums[i - 1]*res[i-1];
    }
    //后缀和处理
    for(let i = nums.length - 2;i >= 0;i--){
        rightArr[i] = nums[i + 1] * rightArr[i + 1]; 
    }
    //最后统计结果
    for(let i = 0;i < nums.length;i++){
        res[i] = res[i] * rightArr[i];
    }
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

但这个仍然是用到了rightArr数组，空间复杂度仍然不达标。

【第二次改进】：
我们发现，rightArr数组也是多余的。

var productExceptSelf = function(nums) {
    var res = new Array(nums.length);           //存放前缀积
    res.fill(1);
    //前缀和处理
    for(let i = 1;i < nums.length;i++){
        res[i] = nums[i - 1]*res[i-1];
    }
    //直接用一个变量就可以处理后缀积
    var right = 1;
    for(let i = nums.length - 1;i >= 0;i--){
        res[i] = res[i] * right;
        right *= nums[i];
    }
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

题目中answer数组是不计入空间复杂度的，所以这个代码就已经达标。