除自身以外数组的乘积

给你一个整数数组 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 <= 10^5
• -30 <= nums[i] <= 30
• 输入保证数组 answer[i] 在 32 位整数范围内

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

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

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> prefix(n, 1);
        vector<int> suffix(n, 1);
        vector<int> answer(n, 1);

        for (int i = 1; i < n; i++)
        {
            prefix[i] = prefix[i - 1] * nums[i - 1];
        }

        for (int i = n - 2; i >= 0; i--)
        {
            suffix[i] = suffix[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < n; i++)
        {
            answer[i] = prefix[i] * suffix[i];
        }

        return answer;
    }
};

解法二（输出数组 + 后缀变量）：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> answer(n, 1);

        for (int i = 1; i < n; i++)
        {
            answer[i] = answer[i - 1] * nums[i - 1];
        }

        int suffix = 1;
        for (int i = n - 1; i >= 0; i--)
        {
            answer[i] *= suffix;
            suffix *= nums[i];
        }

        return answer;
    }
};

核心思想

题目要求：

answer[i] = nums 中除了 nums[i] 以外所有元素的乘积

也就是说，对于位置 i，答案由两部分组成：

1. i 左边所有元素的乘积
2. i 右边所有元素的乘积

因此：

answer[i] = 左侧乘积 * 右侧乘积

这就是前缀乘积和后缀乘积的思路。

注意，题目要求不能使用除法。

如果用所有元素乘积除以 nums[i]，不仅违反题意，而且遇到 0 时也会出问题。

而前缀乘积 + 后缀乘积不需要除法，所以可以自然处理数组中存在 0 的情况。

前缀乘积和后缀乘积

定义：

prefix[i] 表示 nums[i] 左边所有元素的乘积。

也就是：

prefix[i] = nums[0] * nums[1] * ... * nums[i - 1]

如果 i = 0，左边没有元素，所以：

prefix[0] = 1

这里的 1 表示乘法单位元，任何数乘以 1 都不变。

同理，定义：

suffix[i] 表示 nums[i] 右边所有元素的乘积。

也就是：

suffix[i] = nums[i + 1] * nums[i + 2] * ... * nums[n - 1]

如果 i = n - 1，右边没有元素，所以：

suffix[n - 1] = 1

最终：

answer[i] = prefix[i] * suffix[i]

公式推导

对于任意位置 i，题目要求的乘积是：

nums[0] * nums[1] * ... * nums[i - 1] * nums[i + 1] * ... * nums[n - 1]

把它拆成左右两部分：

左边：

nums[0] * nums[1] * ... * nums[i - 1]

右边：

nums[i + 1] * nums[i + 2] * ... * nums[n - 1]

所以：

answer[i] = prefix[i] * suffix[i]

其中：

prefix[i] = prefix[i - 1] * nums[i - 1]

suffix[i] = suffix[i + 1] * nums[i + 1]

这就是代码中两次遍历的来源。

为什么可以处理数组中的 0

例如：

nums = [-1,1,0,-3,3]

如果使用除法，就会遇到除以 0 的问题。

但前缀乘积和后缀乘积不会除以任何数，只是做乘法。

当计算 answer[2] 时，位置 2 的元素是 0，但我们并不使用它。

此时：

• 左侧乘积是 (-1) * 1 = -1
• 右侧乘积是 (-3) * 3 = -9

所以：

answer[2] = (-1) * (-9) = 9

而其他位置的左右两侧至少有一边会包含这个 0，所以答案自然变成 0。

这正好得到：

[0,0,9,0,0]

空间优化

解法一用了三个数组：

• prefix
• suffix
• answer

但其实输出数组 answer 不算额外空间。

所以可以先把 answer[i] 存成 prefix[i]。

也就是第一遍从左到右：

answer[i] = answer[i - 1] * nums[i - 1];

此时：

answer[i] = nums[0] * nums[1] * ... * nums[i - 1]

也就是位置 i 左边所有元素的乘积。

然后第二遍从右到左，用变量 suffix 维护当前位置右边所有元素的乘积。

在遍历到位置 i 时：

answer[i] *= suffix;

此时 answer[i] 原本是左侧乘积，suffix 是右侧乘积，二者相乘就是最终答案。

之后再更新：

suffix *= nums[i];

表示下一轮往左走时，当前 nums[i] 就会成为右侧元素的一部分。

正确性证明

我们证明解法二返回的 answer 满足题意。

结论 1：第一遍遍历后，answer[i] 等于 i 左边所有元素的乘积

初始时：

answer[0] = 1

因为下标 0 左边没有元素。

对于 i >= 1，代码执行：

answer[i] = answer[i - 1] * nums[i - 1];

如果 answer[i - 1] 是下标 i - 1 左边所有元素的乘积：

nums[0] * nums[1] * ... * nums[i - 2]

那么乘上 nums[i - 1] 后，正好得到：

nums[0] * nums[1] * ... * nums[i - 1]

也就是下标 i 左边所有元素的乘积。

所以第一遍结束后，answer[i] 正确保存了左侧乘积。

结论 2：第二遍遍历时，suffix 等于当前位置右边所有元素的乘积

第二遍从右往左开始时：

suffix = 1

对于最右边位置 n - 1，右边没有元素，所以右侧乘积是 1，正确。

每处理完一个位置 i 后，代码执行：

suffix *= nums[i];

这表示当下一轮来到 i - 1 时，nums[i] 已经位于它的右侧。

所以 suffix 会始终表示当前位置右边所有元素的乘积。

结论 3：最终 answer[i] 等于除自身以外所有元素的乘积

根据结论 1，进入第二遍时：

answer[i] = i 左边所有元素的乘积

根据结论 2，处理位置 i 时：

suffix = i 右边所有元素的乘积

代码执行：

answer[i] *= suffix;

所以此时：

answer[i] = 左侧乘积 * 右侧乘积

也就是：

nums[0] * ... * nums[i - 1] * nums[i + 1] * ... * nums[n - 1]

这正是题目要求的结果。

因此算法正确。

举例理解

以：

nums = [1,2,3,4]

为例。

第一遍得到左侧乘积：

此时：

answer = [1,1,2,6]

第二遍从右往左维护右侧乘积：

• i = 3，右侧乘积是 1，answer[3] = 6 * 1 = 6
• i = 2，右侧乘积是 4，answer[2] = 2 * 4 = 8
• i = 1，右侧乘积是 3 * 4 = 12，answer[1] = 1 * 12 = 12
• i = 0，右侧乘积是 2 * 3 * 4 = 24，answer[0] = 1 * 24 = 24

最终：

answer = [24,12,8,6]

复杂度分析

解法一

• 从左到右计算前缀乘积一次
• 从右到左计算后缀乘积一次
• 最后再遍历一次生成答案
• 时间复杂度：O(n)
• 使用 prefix、suffix 两个额外数组
• 空间复杂度：O(n)

解法二

• 从左到右遍历一次
• 从右到左遍历一次
• 时间复杂度：O(n)
• 除了输出数组，只使用一个 suffix 变量
• 空间复杂度：O(1)

如果按照进阶要求，推荐使用解法二。