238 除了自身以外数组的乘积

一、题目

238. 除了自身以外数组的乘积

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

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

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


二、题解

解法一：前缀乘积 + 后缀乘积

我们可以先算：

left[i]  = nums[i] 左边所有数的乘积right[i] = nums[i] 右边所有数的乘积

最后：

answer[i] = left[i] * right[i]

但是这样需要额外两个数组，空间复杂度是 O(n)。

解法二：优化空间，直接用 answer 数组

第一次遍历：存左边乘积 nums = [1, 2, 3, 4]第一次遍历后：answer = [1, 1, 2, 6] 含义是：

answer[0] = 1        // 0 左边没有数
answer[1] = 1        // 1 左边是 1
answer[2] = 1 * 2
answer[3] = 1 * 2 * 3

第二次遍历：乘上右边乘积

从右往左遍历，用一个变量 right 记录当前位置右边所有数的乘积。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];

        // left 表示当前位置左边所有元素的乘积
        int left = 1;

        for (int i = 0; i < n; i++) {
            answer[i] = left;
            left *= nums[i]; //先把当前位置左边所有数的乘积存进去
        }

        // right 表示当前位置右边所有元素的乘积
        int right = 1;

        for (int i = n - 1; i >= 0; i--) {
            answer[i] *= right;
            right *= nums[i]; //原来 answer[i] 里面已经有左边乘积了，现在再乘上右边乘积。
        }

        return answer;
    }
}

时间复杂度：$O(n)$

空间复杂度：$O(1)$