除自身以外数组的乘积

问题拆解

给定数组 nums，返回数组 answer，其中 answer[i] 等于除 nums[i] 之外所有元素的乘积。题目明确要求不能用除法——否则“全体乘积除以自己”一行就写完了，而且除法还会被 0 卡住：数组里有一个 0 时，除法根本没法做。

不许除，那就换个分解方式。answer[i] 恰好等于两段乘积的拼接：i 左边所有数的积，乘上 i 右边所有数的积。左边的积从左往右可以递推出来，右边的积从右往左也可以递推出来，各扫一趟就齐了。

“除自身以外”不是全局量除以局部量，而是左右两个前缀量的拼接——这正是禁用除法逼出来的视角。

前缀积一趟、后缀积一趟

直接的写法是开两个数组 left 和 right 分别存前缀积、后缀积，再逐位相乘。但题目进阶要求 O(1) 额外空间（输出数组不计入），做法是：第一趟把前缀积直接写进 answer，第二趟从右往左，用一个变量滚动维护后缀积，边走边乘上去。

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] ans = new int[n];
    ans[0] = 1;
    for (int i = 1; i < n; i++) {
        ans[i] = ans[i - 1] * nums[i - 1]; // i 左侧所有数的积
    }
    int suffix = 1; // 滚动维护 i 右侧所有数的积
    for (int i = n - 1; i >= 0; i--) {
        ans[i] *= suffix;
        suffix *= nums[i];
    }
    return ans;
}

def productExceptSelf(nums: List[int]) -> List[int]:
    n = len(nums)
    ans = [1] * n
    for i in range(1, n):
        ans[i] = ans[i - 1] * nums[i - 1]  # i 左侧所有数的积

    suffix = 1  # 滚动维护 i 右侧所有数的积
    for i in range(n - 1, -1, -1):
        ans[i] *= suffix
        suffix *= nums[i]

    return ans

func productExceptSelf(nums []int) []int {
    n := len(nums)
    ans := make([]int, n)
    ans[0] = 1
    for i := 1; i < n; i++ {
        ans[i] = ans[i-1] * nums[i-1] // i 左侧所有数的积
    }
    suffix := 1 // 滚动维护 i 右侧所有数的积
    for i := n - 1; i >= 0; i-- {
        ans[i] *= suffix
        suffix *= nums[i]
    }
    return ans
}

pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    let mut ans = vec![1; n];
    for i in 1..n {
        ans[i] = ans[i - 1] * nums[i - 1]; // i 左侧所有数的积
    }
    let mut suffix = 1; // 滚动维护 i 右侧所有数的积
    for i in (0..n).rev() {
        ans[i] *= suffix;
        suffix *= nums[i];
    }
    ans
}

第一趟结束时 ans[i] 存的是 nums[0..i-1] 的积，注意递推用的是 nums[i - 1] 而不是 nums[i]——前缀积“不含自己”，下标错一位是这题最容易写错的地方。第二趟里两行的顺序也不能颠倒：必须先把 suffix（此刻还不含 nums[i]）乘到 ans[i] 上，再让 suffix 吸收 nums[i]，否则“除自身以外”就变成“含自身”了。

复杂度

指标	复杂度	原因
时间	`O(n)`	正反各扫一遍
空间	`O(1)`	输出数组不计入，额外只有一个滚动变量

可以迁移的模式

“去掉位置 i 的某种聚合量”通常可以拆成前缀聚合 × 后缀聚合，前缀和、前缀异或同理；
两个辅助数组中的一个如果只被顺序消费一次，就能退化成一个滚动变量；
题目禁用某个“显然”的操作（这里是除法）时，往往是在提示存在结构上更稳健的分解——除法版本连 0 都处理不了。

左右各补一半的思路一旦建立，这题剩下的只是两个循环里的下标细节。