Amazon AS：不用除法求除自身外乘积，零与溢出怎么处理？

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 空间口径不计必须返回的输出数组；若把输出也算入，输出n项本身Ω(n)。
• 训练Python整数精确计算；固定宽度环境须确定溢出、模数或bigint政策。空积记1。

解题路线

1. 第一遍out[i]记录所有左侧值乘积，prefix从1起，每次写出之后再乘当前值。第二遍右向左，suffix为严格右侧乘积，将out[i]乘suffix后再纳入当前值。
2. 循环不变量表明out[i]=左积·右积恰好漏掉values[i]且包含其他项各一次，不需要除法。两个方向的更新顺序是保证排除自身的关键。
3. 零自然被处理：一个零只会让零所在位置得到其他非零项乘积；两零时每个输出至少包含一个零。无须单独分支，但必须测这两类。
4. log+exp是近似路线，负值需跟踪符号、零需特判、浮点误差可令整数结果错一单位甚至更多。若输出必须精确，用范围证明、检查乘法或大整数；不能把取log当无损溢出修复。

手动走一遍

训练例[2,0,3]→[0,6,0]；[0,0,3]→[0,0,0]；[-2,3,4]→[12,-8,-6]；单元素[7]训练输出[1]。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def product_except_self(values):
    """Output space excluded from O(1) auxiliary space; Python integer arithmetic."""
    out = [1] * len(values)
    prefix = 1
    for i,value in enumerate(values):
        out[i] = prefix
        prefix *= value
    suffix = 1
    for i in range(len(values)-1, -1, -1):
        out[i] *= suffix
        suffix *= values[i]
    return out

复杂度

单位成本乘法模型O(n)时间、O(1)辅助空间、O(n)输出；大整数的位复杂度随积的位数增长，Python避免固定宽度溢出不等于每次乘法永远O(1)。

易错点与追问

容易失分的边界

• prefix先乘当前值再写出。
• 输出空间也计算却声称总O(1)。
• 用log/exp保证精确整数。

继续深挖

• 固定模数怎样改？
• 只允许固定宽度整数怎样证明范围？
• 动态点更新和单点除自身查询能否用线段树？