力扣热门100题之除自身意外数组的成绩【中等】

题目描述

给你一个整数数组 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]

提示：

---

解法1 总积法

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    let multRes=1;
    let isZero=false;
    nums.forEach((v)=>{
        if(v!=0){
            multRes*=v;
        }else{
            isZero=true;
        }
    })
    let res=[]
    if(isZero){
        for(let i=0;i<nums.length;i++){
            if(nums[i]==0){
                nums[i]=1
                if(nums.indexOf(0)!=-1){
                    res.push(0);
                }else{
                    res.push(multRes);
                }
                nums[i]=0;
            }else{
                res.push(0);
            }
        }
    }else{ 
        nums.forEach((v)=>{
            res.push(multRes/v);
        })
    }
    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
25
26
27
28
29
30
31
32
33
34
35
36

执行结果

解法2 左右乘积列表

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

执行结果：

左右乘积列表优化

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    let l=[1] //l[i] 表示i左侧所有元素的乘积
    const len=nums.length;
    let r=1;//r为左侧的乘积
    for(let i=1;i<len;i++){
        l[i]=l[i-1]*nums[i-1];
    }
    for(let i=len-1;i>=0;i--){
        l[i]=l[i]*r;
        r*=nums[i];
    }
   
    return l;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

执行结果：