LC238　除了自身以外数组的乘积¶

中等通过率 77.7%python3核心代码模式普通数组样例通过牛客 AC数组前缀和

一句话

前缀积与后缀积各扫一遍，答案数组当中间存储，不用除法。

解题思路¶

这题考什么¶

answer[i] 要的是「除 nums[i] 外全体的乘积」。若允许除法，先求总积再除以 nums[i] 就完事了，但 nums 里可能有 0：出现一个 0 时总积为 0，除以它是除零错误，只能改成「统计 0 的个数 + 非零元素的积」再分三种情形讨论。题目干脆禁掉除法，逼出更干净的思路。

把乘积按位置劈成两半：

answer[i] = (nums[0] * nums[1] * … * nums[i-1]) * (nums[i+1] * … * nums[n-1])
          =        前缀积 pre[i]                *        后缀积 suf[i]

两个因子都不含 nums[i]，天然绕开了除法与 0 的麻烦。而 pre 与 suf 各自都能一趟递推出来：pre[0] = 1（空积），pre[i] = pre[i-1] * nums[i-1]； suf[n-1] = 1，suf[i] = suf[i+1] * nums[i+1]。这就是乘法版的前缀和，见前缀和与差分。

照定义要开 pre、suf 两个数组，是 O(n) 额外空间。进阶要求 O(1)（输出数组不计），做法是把答案数组当草稿纸：第一趟从左往右，把 pre[i] 直接写进 answer[i]；第二趟从右往左，用一个滚动变量 suf 边走边乘进去。suf 只用到相邻一项，不必存成数组，于是除输出外只剩两个整数变量。

数据规模与复杂度¶

2 <= n <= 1e5，-30 <= nums[i] <= 30，题目保证任意前缀积与后缀积都落在 32 位整数范围内（即绝对值不超过约 2.1e9）。时间 O(n)：两趟线性扫描。除输出数组外空间 O(1)。对每个 i 现乘一遍其余 n-1 个数是 O(n^2) = 1e10 次乘法，Python 下不可行。值域看着很小（最大 30），但别被误导：若没有题目那句保证，1e5 个 30 相乘是天文数字——Python 的大整数不会溢出，只会让单次乘法从 O(1) 退化，换成 C++ 的 int 则直接溢出成垃圾值。

坑在哪¶

不能用除法，这不只是题目的限制，也是正确性问题：nums 含 0 时总积为 0，除法版要额外分「0 的个数为 0 / 1 / 2 及以上」三种情形，样例 2 的 [-1,1,0,-3,3] 正是为此设计的。前缀后缀积的写法对 0 毫无特殊处理。
前缀积的下标偏移是本题最容易写错的地方：answer[i] 要的是 nums[0..i-1] 的积，不含 nums[i]。所以循环体必须是「先把当前的 pre 写进 answer[i]，再把 nums[i] 乘进 pre」。顺序反了就把自己也乘进去了，答案变成整体积。后缀那一趟同理：先 answer[i] *= suf，再 suf *= nums[i]。
pre 与 suf 的初始值都是 1，因为空乘积等于 1（乘法单位元）。初始化成 0 会让整个答案全变成 0。这与前缀和取 0 起步是同一个道理，只是单位元从加法的 0 换成了乘法的 1。
第二趟必须从右往左走：suf 递推依赖右边的元素，从左往右扫拿不到。 range 的写法是 range(n - 1, -1, -1)，终点写 -1 才能取到下标 0，写成 range(n - 1, 0, -1) 会漏掉最左那一项。
answer 的初值（本题解用 1）不影响结果，第一趟会把每个位置整个覆写掉。但不能跳过第一趟直接在第二趟里乘，那样 answer 里全是初值 1，只会得到后缀积。
输出数组不算额外空间，这是题面进阶明确写的口径。用 answer 当草稿纸是合法的，不算「偷偷多开了 O(n)」。
严格比对：每个位置的乘积唯一，输出顺序与输入一一对应，没有多解。

样例复核¶

nums = [1, 2, 3, 4]，期望 [24, 12, 8, 6]。第一趟（从左，answer[i] 先收 pre，pre 再吃掉 nums[i]）：

i=0  answer[0] = 1（空积）    pre 变成 1
i=1  answer[1] = 1            pre 变成 2
i=2  answer[2] = 2            pre 变成 6
i=3  answer[3] = 6            pre 变成 24
此时 answer = [1, 1, 2, 6]，正是各位置的前缀积。

第二趟（从右，answer[i] 先乘 suf，suf 再吃掉 nums[i]）：

i=3  answer[3] = 6 * 1 = 6    suf 变成 4
i=2  answer[2] = 2 * 4 = 8    suf 变成 12
i=1  answer[1] = 1 * 12 = 12  suf 变成 24
i=0  answer[0] = 1 * 24 = 24  suf 变成 24

得 [24, 12, 8, 6]，与样例一致。含 0 的样例 2 也走同一条路：[-1,1,0,-3,3] 的前缀积是 [1,-1,-1,0,0]，后缀积是 [0,0,-9,3,1]（注意下标 2 的后缀积 -9 跳过了 nums[2] = 0 本身），对位相乘得 [0,0,9,0,0]，与期望一致——全程没有一次除法。

参考实现¶

solutions/leetcode/LC238/sol.py
from typing import List, Optional


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        # 输出数组按题面进阶的口径不计入额外空间，所以它可以兼作草稿纸。
        # 这里的初值 1 只是占位，第一趟会把每个位置整个覆写掉
        answer = [1] * n
        # 第一趟从左往右，把「不含自己的前缀积」写进 answer。
        # pre 起步取 1 是因为空乘积等于 1（乘法单位元），取 0 会让全部答案变成 0
        pre = 1
        for i in range(n):
            # 顺序是死规矩：先写后乘。此刻 pre 还是 nums[0..i-1] 的积，
            # 恰好不含 nums[i]；反过来先乘再写就把自己也算进去了
            answer[i] = pre
            pre *= nums[i]
        # 第二趟必须从右往左，因为后缀积依赖右边的元素。
        # 终点写 -1 才能取到下标 0，写成 range(n - 1, 0, -1) 会漏掉最左一项
        suf = 1
        for i in range(n - 1, -1, -1):
            # 同样是先乘后更新：此刻 suf 是 nums[i+1..n-1] 的积，不含 nums[i]。
            # suf 只用到相邻一项，不必存成数组，这就是把空间压到 O(1) 的地方
            answer[i] *= suf
            suf *= nums[i]
        return answer

LC238 除了自身以外数组的乘积¶