除自身以外数组的乘积怎么不用除法在 O(n) 内完成？

简化版

要求 res[i] = 数组里除了 a[i] 以外所有元素的乘积,且不能用除法。用前缀积 × 后缀积:res[i] = (i 左边所有元素的积) × (i 右边所有元素的积)。先从左到右算前缀积,再从右到左算后缀积并直接乘进结果。O(n) 时间,用滚动变量可做到 O(1) 额外空间(输出数组不算)。

详细版

两趟 + 滚动变量(O(1) 额外空间):

int[] productExceptSelf(int[] a) {
    int n = a.length;
    int[] res = new int[n];
    // 第一趟：res[i] = 左边所有元素的积（前缀积）
    res[0] = 1;
    for (int i = 1; i < n; i++)
        res[i] = res[i - 1] * a[i - 1];
    // 第二趟：乘上右边所有元素的积（后缀积，用滚动变量 right）
    int right = 1;
    for (int i = n - 1; i >= 0; i--) {
        res[i] *= right;           // 左边积 × 右边积
        right *= a[i];             // 更新右边积
    }
    return res;
}

第一趟:res[i] 存「i 左边所有元素的积」(前缀积)。
第二趟:用变量 right 累积「i 右边所有元素的积」,乘进 res[i]。
只用输出数组 + 一个变量,O(1) 额外空间。

完整版教学

一、为什么不能用除法

最直接的想法:先算所有元素的总积,再对每个位置 res[i] = 总积 / a[i]。但题目禁止除法,原因通常是:

有 0 的情况:如果数组里有 0,除法会除零出错;有一个 0 时所有非零位置的结果都是 0、0 位置是其余的积,有两个及以上 0 时全是 0——用除法要特判很麻烦。
精度/整数除法问题。

所以要绕开除法,用「左边积 × 右边积」的思路,天然避开除零。

二、核心:res[i] = 左边积 × 右边积

除 a[i] 外所有元素的积 可以拆成两部分:

res[i] = (a[0] × a[1] × ... × a[i-1])   ← i 左边所有元素的积（前缀积）
       × (a[i+1] × ... × a[n-1])         ← i 右边所有元素的积（后缀积）

左右两部分都不包含 a[i] 自己,乘起来正好是「除自身外的乘积」。前缀积负责左边、后缀积负责右边,这是本题的核心拆分。

三、两趟遍历实现

第一趟(从左到右)算前缀积:res[i] 先存「i 左边所有元素的积」。res[0] = 1(左边没有元素,积为 1),res[i] = res[i-1] * a[i-1]。
第二趟(从右到左)乘后缀积:用一个变量 right 从右往左累积「i 右边所有元素的积」(初始 right = 1)。对每个 i:res[i] *= right(把右边积乘进去),然后 right *= a[i](更新给下一个更左的位置用)。

两趟下来,res[i] = 左边积 × 右边积,正是答案。

四、为什么能做到 O(1) 额外空间

朴素做法可能开两个数组(前缀积数组 + 后缀积数组),O(n) 额外空间。优化的关键:

前缀积直接存进输出数组 res(不单开数组)。
后缀积用一个滚动变量 right,边遍历边乘,不存数组。

于是除了必须的输出数组 res,只额外用了一个变量 right,O(1) 额外空间(题目通常规定输出数组不计入空间复杂度)。这是本题的进阶考点。

五、走一个例子

a = [1, 2, 3, 4]
第一趟（前缀积）：res = [1, 1, 2, 6]
                        (1) (1) (1×2) (1×2×3)
第二趟（后缀积 right 从右）：
  i=3: res[3]=6×1=6,  right=1×4=4
  i=2: res[2]=2×4=8,  right=4×3=12
  i=1: res[1]=1×12=12, right=12×2=24
  i=0: res[0]=1×24=24, right=24×1=24
结果 res = [24, 12, 8, 6] ✓

六、和前缀和的联系

这题是「前缀积」——把前缀和的加法换成乘法。前缀和 prefix[i] = 左边元素的和,前缀积 = 左边元素的积。前缀和用「相减」得区间和,但乘法的逆是除法,而这题禁用除法,所以不能像前缀和那样「总积 ÷ 前缀积」得后缀,只能前后两趟分别算前缀积和后缀积。这也解释了为什么它比前缀和的区间查询多一趟——除法被禁,补不了。

七、从公式证明到手算闭环

这道题成立的核心是：第一趟结束时 res[i] 是 i 左侧乘积；第二趟用变量 right 乘入 i 右侧乘积且不包含 a[i]。先明确每个数组槽或哈希键的数学含义，代码中的下标偏移才不是死记硬背。

res[i] = product(a[0..i-1]) * product(a[i+1..n-1])
left pass: res[i] = left; left *= a[i]
right pass: res[i] *= right; right *= a[i]

带数字推演：[1,2,3,4] 第一趟 res 为 [1,1,2,6]，逆向乘右积后得到 [24,12,8,6]。手算时同时列出原数组、辅助状态和本轮新增答案，能够直接发现端点偏一、初始化遗漏以及更新顺序错误。

核对维度	本题结论
正确性依据	第一趟结束时 res[i] 是 i 左侧乘积；第二趟用变量 right 乘入 i 右侧乘积且不包含 a[i]
复杂度	两趟 O(n)，除输出外 O(1) 额外空间
关键边界	算法天然处理一个或多个 0，无需特判除法；题目若不保证乘积范围则需要更宽类型；输出数组通常不计额外空间

记忆钩子：不要先背代码，先说清辅助状态“代表哪一段”；公式只是把重叠部分消掉或把边界影响传播出去。

八、实现边界与测试策略

实现时最需要警惕的是：算法天然处理一个或多个 0，无需特判除法；题目若不保证乘积范围则需要更宽类型；输出数组通常不计额外空间。这不是语法细节，而是决定算法是否仍满足题目语义的前提。

提交前应分别验证：

空数组或最小合法规模，确认哨兵位置和初始化。
查询或更新紧贴左、上边界，确认没有访问负下标。
查询或更新紧贴右、下边界，确认“终点后一位”不会越界。
包含 0、负数或重复前缀的样例，确认频次与取模语义。
大数输入，确认累计和、乘积或答案数量的整数类型足够。

如果需求从离线变成在线，或从单次恢复变成更新查询交错，原方法可能不再合适。此时应根据操作类型改用树状数组、线段树、二维结构或其他能维护动态状态的数据结构，而不是强行沿用静态前缀模型。

九、常见误区与追问

误区：总乘积除以自身最简单且总正确。 零元素会除零，题目也明确禁止除法。
误区：第二趟 right 应先乘 a[i]。 那会错误地把自身包含进结果。
误区：O(1) 空间意味着不需要结果数组。 通常是“不计输出数组”，左右积之一复用输出。
追问：为什么能处理两个零？ 任何位置的“除自身乘积”仍包含至少一个零，结果全为零。
追问：一个零时结果怎样？ 只有零所在位置可能非零，值为其余元素乘积。
追问：如何处理乘法溢出？ 按题目范围选 long、BigInteger 或明确模数，不能悄悄溢出。

十、加强记忆

除自身外的乘积(禁用除法)= 前缀积 × 后缀积:res[i] = 左边所有元素积 × 右边所有元素积(都不含 a[i])。两趟:第一趟从左到右把前缀积存进 res;第二趟从右到左用滚动变量 right 累积后缀积并乘进 res。O(n) 时间、O(1) 额外空间(输出数组不计)。禁除法是因为有 0 时除法要特判;它是「乘法版前缀和」,但因除法被禁,必须前后两趟。

简化版

详细版