【面试经典150题】除自身以外数组的乘积 JavaScript

题目链接

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

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

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

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

---

思路1：prefix + suffix

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    const prefix = [];
    const suffix = [];
    prefix[0] = 1;
    suffix[nums.length-1] = 1;
    for(let i = 1; i < nums.length; i++){
        prefix[i]=nums[i-1]*prefix[i-1];
    }
    for(let i = nums.length-2; i>=0; i--){
        suffix[i]=nums[i+1]*suffix[i+1];
    }
    return nums.map((value,index,arr)=>suffix[index]*prefix[index]);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

时间复杂度：O(n)

空间复杂度：O(n)

---

思路2：优化，不使用除结果数组之外的额外空间

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    const n=nums.length;
    const answer=new Array(n);
    let left = 1;
    for(let i=0;i<n;i++){
        answer[i] = left;
        left*=nums[i];
    }
    let right=1;
    for(let i=n-1;i>=0;i--){
        answer[i]*=right;
        right*=nums[i];
    }
    return answer;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19