除自身以外数组的乘积

问题陈述

给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
输入: [1,2,3,4]
输出: [24,12,8,6]

思路分析

对于给定索引 i，我们将使用它左边所有数字的乘积乘以右边所有数字的乘积得到除自身以外数组的乘积。

初始化两个空数组 L 和 R。对于给定索引 i，L[i] 代表的是 i 左侧所有数字的乘积，R[i] 代表的是 i 右侧所有数字的乘积。
我们需要用两个循环来填充 L 和 R 数组的值。对于数组 L，L[0] 应该是 1，因为第一个元素的左边没有元素。对于其他元素：L[i] = L[i-1] * nums[i-1]。
同理，对于数组 R，R[length-1] 应为 1。length 指的是输入数组的大小。其他元素：R[i] = R[i+1] * nums[i+1]。
当 R 和 L 数组填充完成，我们只需要在输入数组上迭代，且索引 i 处的值为：L[i] * R[i]。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] productExceptSelf(int[] nums){
        int len=nums.length;
        int[] L=new int[len];
        int[] R=new int[len];
        L[0]=1,R[len-1]=1;
        for(int i=1;i<len;i++){
            L[i]=L[i-1]*nums[i-1];
        }
        for(int j=len-2;j>=0;j--){
            R[j]=R[j+1]*nums[j+1];
        }
        int[] res=new int[len];
        for(int k=0;k<len;k++){
            res[k]=L[k]*R[k];
        }
        return res;
    }
}

优化，对R不构建数组,L用res表示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int[] productExceptSelf(int[] nums){
        int len=nums.length;
        int[] res=new int[len];
        res[0]=1;
        for(int i=1;i<len;i++){
            res[i]=res[i-1]*nums[i-1];
        }
        int R=1;
        for(int j=len-1;j>=0;j--){
            res[j]*=R;
            R*=nums[j];
        }
        return res;
    }
}