📃 题目描述

题目链接：238. 除自身以外数组的乘积 (opens new window)

🔔 解题思路

我们不必将所有数字的乘积除以给定索引处的数字得到相应的答案，而是利用索引左侧所有数字的乘积和右侧所有数字的乘积（即前缀与后缀）相乘得到答案。

对于给定索引 i，我们将使用它左边所有数字的乘积乘以右边所有数字的乘积

class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        int[] res = new int[nums.length];
		
        // nums[i] 左边所有数的乘积（不包括 nums[i]）
        int[] leftAccumulate = new int[nums.length];
        // nums[i] 右边所有数的乘积（不包括 nums[i]）
        int[] rightAccumulate = new int[nums.length];
        // base case
        leftAccumulate[0] = 1;
        rightAccumulate[nums.length - 1] = 1;
        
        for (int i = 1; i  < nums.length; i ++) {
            leftAccumulate[i] = leftAccumulate[i - 1] * nums[i - 1];
        }
        for (int i = nums.length - 2; i >= 0; i --) {
            rightAccumulate[i] = rightAccumulate[i + 1] * nums[i + 1]; 
        }

        for (int i = 0; i < nums.length; i ++) {
            res[i] = leftAccumulate[i] * rightAccumulate[i];
        }

        return res;
    }
}

我们用了两个数组，一个用来记录左边乘积，一个用来记录右边乘积，可以优化下，其中一个数组我们直接用一个变量来存就行了

比如我们不去构造 rightAccumulate 数组。而是用一个遍历来跟踪右边元素的乘积。并更新数组 res[i] = leftAccumulate[i] * rightAccumulate;。然后 rightAccumulate 更新为 rightAccumulate *= nums[i];，其中变量 rightAccumulate 表示的就是索引右侧数字的乘积。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        int[] res = new int[nums.length];

        int[] leftAccumulate = new int[nums.length];
        // base case
        leftAccumulate[0] = 1;
        
        for (int i = 1; i  < nums.length; i ++) {
            leftAccumulate[i] = leftAccumulate[i - 1] * nums[i - 1];
        }

        int rightAccumulate = 1;
		
        // 注意这里是从后往前遍历
        for (int i = nums.length - 1; i >= 0; i --) {
            res[i] = leftAccumulate[i] * rightAccumulate;
            rightAccumulate *= nums[i];
        }

        return res;
    }
}

💥 复杂度分析

• 空间复杂度：
• 时间复杂度：