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]

提示：

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

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

解法

正常的想法就是先求一遍数组总乘积，然后遍历一遍数组用总乘积除以当前位置的元素即可。但是题目要求不能使用除法。

其实每个位置元素的“其余各元素的乘积”其实就是元素“左边位置的乘积 * 右边元素的乘积”，如下所示：

原数组：        [1       2       3       4]
左部分的乘积：    1       1      1*2    1*2*3
右部分的乘积：  2*3*4    3*4      4       1
结果：        1*2*3*4  1*3*4   1*2*4  1*2*3*1

因此需要进行三次遍历，第一次遍历用于求左部分的乘积，第二次遍历在求右部分的乘积，第三次将最后的计算结果求出来。代码如下：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] leftProduct = new int[nums.length];
        int[] rightProduct = new int[nums.length];
        int left = 0, right = nums.length - 1;
        while (left < nums.length) {
            // 左边元素的乘积
            leftProduct[left] = left == 0 ? 1 : nums[left - 1] * leftProduct[left - 1];
            // 右边元素的乘积
            rightProduct[right] = right == nums.length - 1 ? 1 : nums[right + 1] * rightProduct[right + 1];
            left++;
            right--;
        }
        int[] result = new int[nums.length];
        for (int i = 0; i < result.length; i++) {
            result[i] = leftProduct[i] * rightProduct[i];
        }
        return result;
    }
}

优化

其实没必要三次遍历，上面的过程需要两次正序遍历，一次倒序遍历，其实两次正序遍历可以合到一起，一边遍历一遍计算左边元素的乘积即可，而且还可以省下一个数组的空间。代码如下：

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] rightProduct = new int[nums.length];
        rightProduct[nums.length - 1] = 1;
        int right = nums.length - 2;
        while (right >= 0) {
            rightProduct[right] = nums[right + 1] * rightProduct[right + 1];
            right--;
        }
        int[] result = new int[nums.length];
        result = rightProduct[0];
        int left = 1, leftProduct = nums[0];
        while (left < nums.length) {
            leftProduct = leftProduct * nums[left - 1];
            result[left] = leftProduct * rightProduct[left];
            left++;
        }
        return result;
    }
}

再次优化

上面的算法时间复杂度 O(2n)，额外空间复杂度 O(n)，那么可以做到进阶要求的那样使用 O(1) 时间复杂度吗？

其实改题目要求的 O(1) 额外空间复杂度并不是和我们常规理解的那样只是用一个中间元素完成计算，题目已经说明“输出数组不被视为额外空间”，所以可以利用输出数组来作为中间元素计算，这样就不会增加所谓的额外空间，只需要将上面的代码稍微调整下就可以了。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        result[nums.length - 1] = 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            result[i] = nums[i + 1] * result[i + 1];
        }

        int leftProduct = 1;
        for (int i = 1; i < nums.length; i++) {
            leftProduct = leftProduct * nums[i - 1];
            result[i] *= leftProduct;
        }
        return result;
    }
}