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

◎

本节目标

分别累计左侧和右侧乘积，在输出数组中合成每个位置的答案。

这道题承接前缀信息与差分：每个答案只依赖它左侧与右侧的累计乘积。

查看原题

题意与约束

返回数组 answer，其中 answer[i] 是除 nums[i] 外所有元素的乘积；不能使用除法。

朴素思路及瓶颈

对每个位置重新遍历数组，并跳过当前位置，可以直接算出答案，但每个元素会在不同位置的计算中被重复相乘，时间复杂度为 O(n²)。使用总乘积再除以当前位置虽然更快，却违反不能使用除法的要求，且遇到零还需额外分类；更合适的做法是复用左右两侧的累计乘积。

两次扫描

第一次从左到右，把位置 i 左侧的乘积写入 answer[i]。第二次从右到左维护滚动的右侧乘积，并乘到同一位置。零自然由乘法传播，不需单独分类。

代码实现

两份源码复用输出数组保存左侧乘积，只额外维护一个右侧滚动乘积。

C++

C++17

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> answer(nums.size(), 1);
        int prefix = 1;
        for (size_t index = 0; index < nums.size(); index++) {
            answer[index] = prefix;
            prefix *= nums[index];
        }

        int suffix = 1;
        for (size_t index = nums.size(); index > 0; index--) {
            answer[index - 1] *= suffix;
            suffix *= nums[index - 1];
        }
        return answer;
    }
};

Python

Python 3

class Solution:
    def productExceptSelf(self, nums: list[int]) -> list[int]:
        answer = [1] * len(nums)
        prefix = 1
        for index, num in enumerate(nums):
            answer[index] = prefix
            prefix *= num

        suffix = 1
        for index in range(len(nums) - 1, -1, -1):
            answer[index] *= suffix
            suffix *= nums[index]
        return answer

复杂度分析

时间复杂度为 O(n)，除输出数组外的额外空间为 O(1)。

易错点

• 在左侧扫描中把当前位置也乘进去。
• 右侧扫描方向写反，重复使用了当前位置的值。

模式迁移

当答案由“当前位置左边的信息”和“右边的信息”共同决定时，可先写一侧累计，再反向乘入另一侧累计；这种分解也适用于前后缀最大值等问题。