如果你正在刷 LeetCode 的热门100题大概率会撞上 238 题《除自身以外数组的乘积》。我第一次看到它脑子里冒出来的解法是先把所有元素乘成一个 total再逐个除以 nums[i]。结果刚想动手就被题目规则按住了——不能用除法。当时我还有点不服气后来把这道题从直觉方案到边界条件完整过了一遍才发现这条限制其实是命题人帮你避坑。我打算按这个顺序讲先从“为什么除法走不通”说起再给左右乘积法的标准解接着把空间压到 O(1) 的原地解法单独讨论 0 这种特殊输入最后延伸到接雨水、前缀和这类同套路题目。照着走一遍你不仅能拿下这道题还能顺手掌握一种很常用的左右扫描套路。1. 为什么“先乘再除”根本走不通1.1 谁都会想到的 total / nums[i] 方案题目描述其实很朴素给定一个整数数组 nums返回一个数组 answer其中 answer[i] 等于数组中除 nums[i] 之外所有元素的乘积。看到这个描述第一直觉一定是先算全数组乘积再逐位相除total 1 for x in nums: total * x return [total // x for x in nums]如果数组里全是正数这段代码在数学上毫无问题时间复杂度 O(n)空间复杂度 O(1)看起来相当完美。LeetCode 之所以专门加一条“不要使用除法”就是因为这条路一旦遇到 0 就会彻底崩掉而且崩得很隐蔽。很多人第一次刷这道题时根本没意识到数组允许出现 0等提交报错才回过头来排查浪费了时间。1.2 单个 0 就把信息抹掉了以 nums [1, 2, 0, 4] 为例total 0。逐个算answer[0] 0 // 1 0结果其实是 2 * 0 * 4 0这个位置恰好是对的answer[1] 0 // 2 0这个位置也是对的answer[2] 0 // 0直接抛异常answer[3] 0 // 4 0这个位置也是对的。问题就出在 answer[2]。它本应是 1 * 2 * 4 8但在 total 里这个 8 已经被那个 0 乘成了 0除数本身又是 0任何语言都没法从 0 反推出 8。换句话说除法方案把整个数组的信息压缩成了一个数一旦压缩过程中出现 0逆向操作就丢失了关键信息。数学上这叫除法是乘法的逆运算但乘法一旦碰到 0 就不是单射了信息不可逆。1.3 多个 0 时特判也不优雅如果数组长成 [0, 1, 0, 3]total 也是 0。这种情况一眼能看出答案是全零数组因为每个位置的“其余元素”里必然包含至少一个 0。真正麻烦的是只有一个 0 的情况除了 0 所在位置能算出一个非零结果其他位置全是 0。想用除法就得先统计 0 的个数个数为 1 时还要单独扫一遍求“去掉那个 0 以后的乘积”再填到对应位置。这套分支逻辑写出来比前缀后缀解法还长而且面试时特别容易把自己绕晕。所以这道题用除法的隐藏成本是为了规避除法反而写出一堆特判代码的可读性和正确性都在下降。1.4 题目的真实用意不要逆运算要拆分把“禁止除法”理解成出题人故意刁难就误解了这道题。它的真实用意是让你放弃“把一个数组揉成一个数再反向解出来”的方向换成更底层的视角每个位置的答案其实由“它左边的乘积”和“它右边的乘积”两块互不干扰的信息组成。你不需要知道全数组的乘积只需要知道每个位置两侧分别乘出来了什么。顺着这个想法走就自然进入了前缀/后缀乘积的框架。这个思路一旦建立你会发现在 LeetCode 大量题目里都能看到它的影子接雨水、前缀和、柱状图中的最大矩形等后面我会展开讲。2. 核心思路把“除自身”拆成“左侧乘积 × 右侧乘积”2.1 一个关键等式对于任意位置 ianswer[i] (nums[0] 到 nums[i-1] 的乘积) × (nums[i1] 到 nums[n-1] 的乘积)我把左边这半段记作 L[i]前缀乘积右边半段记作 R[i]后缀乘积。于是问题被拆成两个完全独立的小任务先填好 L再填好 R最后把对应位置相乘。这个等式看起来简单但它把“除自身以外”这种全局条件变成了“左右两边各看各的最后合并”的局部条件。全局条件往往很难直接计算但局部条件可以用递推轻松搞定这就是这题的核心转化。2.2 前缀乘积 L 怎么递推定义 L[i] nums[0] × nums[1] × ... × nums[i-1]表示从数组开头一直到 i 左侧一个元素为止的乘积。边界是 L[0] 1因为 i 0 时左侧没有任何元素数学上把空集的乘积约定为 1也就是乘法单位元。从第二个位置开始可以递推L[i] L[i-1] × nums[i-1]注意这里的下标是 nums[i-1]不是 nums[i]。原因很简单L[i] 的终点在 i 的左边一个位置也就是 i-1L[i-1] 代表已经乘到了 i-2 位置再乘一个 nums[i-1] 才能覆盖到 i-1。很多第一次写这题的人会下意识写成 L[i-1] * nums[i]导致结果整体错位一位对小样本很难一眼看出来。2.3 后缀乘积 R 怎么递推R[i] nums[i1] × nums[i2] × ... × nums[n-1]表示从 i 右侧一个元素起到数组末尾的乘积。边界是 R[n-1] 1最后一个元素右侧为空集。从右往左递推R[i] R[i1] × nums[i1]同样这里的下标是 nums[i1]不是 nums[i]。每当写这种递推式时我建议你在旁边标注“这个 R[i] 的终点在哪里”只要把终点的下标想清楚索引错误基本就能避免。后缀乘积必须从右往左填因为它依赖靠右位置的已知结果这和前缀乘积必须从左往右填是对称的。2.4 用手算跑一遍 [1, 2, 3, 4]有些读者可能觉得递推公式抽象我直接手工跑一遍。nums [1, 2, 3, 4]。先算 LL[0] 1L[1] L[0] * nums[0] 1 * 1 1L[2] L[1] * nums[1] 1 * 2 2L[3] L[2] * nums[2] 2 * 3 6。再算 RR[3] 1R[2] R[3] * nums[3] 1 * 4 4R[1] R[2] * nums[2] 4 * 3 12R[0] R[1] * nums[1] 12 * 2 24。最终乘积如下表inums[i]L[i]R[i]answer[i]011242412112122324834616输出 [24, 12, 8, 6]和题目示例完全一致。整个计算过程没有出现除法也不需要判断某个位置是不是 0非常统一。这也是我为什么特别喜欢这道题它的正确性和特殊条件彻底解耦代码写出来像流水线一样规整。3. 标准解法左右乘积表空间换时间的教科书答案3.1 算法流程左右乘积表解法就是把上面的手算过程写成循环。流程一共四步初始化两个长度 n 的数组 L 和 R全部填 1从左到右遍历 i 1 到 n-1用 L[i-1] * nums[i-1] 填 L[i]从右到左遍历 i n-2 到 0用 R[i1] * nums[i1] 填 R[i]输出 answer[i] L[i] * R[i]。复杂度非常清晰时间复杂度 O(n)额外空间 O(n)输出数组不计入的情况下。LeetCode 这题的 n 最大可以到 10^5所以 O(n) 是必须的任何 O(n^2) 的暴力做法都没法通过。这也是这个解法能成为标准答案的原因它既没有使用除法又保证了线性时间内完成。3.2 Python 代码from typing import List class Solution: def productExceptSelf(self, nums: List[int]) - List[int]: n len(nums) L [1] * n R [1] * n for i in range(1, n): L[i] L[i - 1] * nums[i - 1] for i in range(n - 2, -1, -1): R[i] R[i 1] * nums[i 1] return [L[i] * R[i] for i in range(n)]这个版本是教科书式写法优点是每一步都对应着清晰的数学含义非常适合在面试里先讲思路、再给代码。你甚至可以边写边念“这里 L 是前缀乘积R 是后缀乘积最后合起来就是答案。”面试官通常不会有任何质疑因为逻辑链条非常完整。3.3 四个容易写错的地方第一个range 的起点。右侧遍历如果写成 range(n - 1, -1, -1)第一次循环就会访问 R[n] 和 nums[n]直接越界。正确写法是从 n-2 开始因为 R[n-1] 已经用初始值 1 表示空乘积了不需要再算。第二个L 和 R 的初始化值。把 [1] * n 写成 [0] * n乘积永远都是 0而且运行时不报错肉眼很难发现。记住口诀前缀和用 0 初始化因为 0 是加法单位元前缀积必须用 1 初始化因为 1 是乘法单位元。第三个递推式里的乘数下标。L[i] 乘的是 nums[i-1]R[i] 乘的是 nums[i1]两个都跟当前位置 i 错开一个位置因为我们要排除“自身”。这个错位正是“除自身以外”的体现写循环时一定要对着式子检查一遍。第四个可以拿一个 n2 的极简样例验证。比如 nums [2, 3]答案应该是 [3, 2]。如果写出 [2, 3] 或者越界报错说明你的边界初始化有问题。这种微型样例在调试时比大样例好用得多一眼就能看清递推方向对不对。3.4 为什么会设置 L[0] 1、R[n-1] 1边界初始化看起来是硬编码其实是数学约定在代码里的自然体现。空乘积定义为 1是为了让递推式从第二步开始仍然成立L[1] L[0] * nums[0]如果 L[0] 不是 1这个式子的语义就被破坏了。同理R[n-1] 必须是 1因为最后一个位置的右侧没有任何元素。这个约定和“空数组的和是 0”完全对称只是一个对应加法、一个对应乘法。理解和记住这一点比背代码重要得多因为一旦题目变形你就能自己推出正确的初始化值。4. 进阶解法原地复用结果数组把额外空间压到 O(1)4.1 关键洞察让结果数组先扮演 L题目里有一个 follow-up能不能只用 O(1) 的额外空间输出数组不计入额外空间。换句话说你必须把左右两个辅助数组省掉把中间结果存进 answer 本身。核心思路不复杂第一趟从左到右不再往 L 里填而是直接把 answer[i] 变成“nums[0] 到 nums[i-1] 的乘积”。也就是说answer 先兼职当 L 用。第二趟从右往左用一个普通变量 R 维护已经扫过的后缀乘积每到一个位置就执行 answer[i] * R这时 answer[i] 就从“左侧乘积”升级成了“左侧乘积 × 右侧乘积”也就是真正的最终答案。整个过程只需要一个额外整数变量 R空间确实压到了 O(1)。4.2 代码实现from typing import List class Solution: def productExceptSelf(self, nums: List[int]) - List[int]: n len(nums) answer [1] * n for i in range(1, n): answer[i] answer[i - 1] * nums[i - 1] R 1 for i in range(n - 1, -1, -1): answer[i] * R R * nums[i] return answer如果面试官要求用 C 写逻辑一模一样class Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint answer(n, 1); for (int i 1; i n; i) { answer[i] answer[i - 1] * nums[i - 1]; } int R 1; for (int i n - 1; i 0; --i) { answer[i] * R; R * nums[i]; } return answer; } };C 里要注意一下类型溢出问题。LeetCode 这题的数据范围比较友好题目保证了任意前缀乘积、后缀乘积以及整体乘积都在 32 位整数范围内所以直接用 int 没问题。但如果自己扩展成更大数据建议换 long long或者用 Python 这种不溢出的语言来兜底。4.3 更新顺序的坑先乘旧 R再更新 R第二趟的循环体是两行answer[i] * R R * nums[i]很多人会把这两行写反变成R * nums[i] answer[i] * R这种写法的含义是先把 nums[i] 乘进 R 再给 answer[i] 用等于把“右侧乘积”里也塞进了当前位置本身。结果就是 answer[i] 比正确答案多乘一个 nums[i]而且不是全部位置统一多乘是每个位置都错位debug 起来非常痛苦。你必须在心里保持一个画面当循环走到位置 i 时R 表示的是“从 i1 到数组末尾所有数的乘积”也就是当前位置右侧还没被处理的元素乘积。所以必须先用这个旧 R 去补乘 answer[i]然后再把 nums[i] 纳入 R为下一个位置 i-1 做准备。顺序反了整个结果数组没有任何一个位置是对的。4.4 两种解法怎么选对比项左右乘积表原地复用辅助数组L 和 R无遍历次数3 趟2 趟额外空间O(n)O(1)可读性思路直白适合讲解需要一点抽象思维面试推荐先讲这个作为 follow-up 给出我自己的习惯是面试时先花一分钟把左右乘积表讲清楚证明 O(n) 时间可以做到然后在“能不能再省空间”的追问下亮出原地版本。这样既展示你懂原理又展示你有空间优化的意识。直接上来写原地版本虽然也能过但可能给面试官一种“背过答案”的感觉少了一次展示思路推进的机会。5. 边界条件专项数组里出现 0 的时候5.1 从官方示例 2 说起LeetCode 官方给的第二个示例是输入 nums [-1, 1, 0, -3, 3]输出 answer [0, 0, 9, 0, 0]。为什么中间那个位置是 9因为 nums[2] 是 0对于下标 2 来说其余四个数是 -1、1、-3、3乘积 (-1) × 1 × (-3) × 3 9。其他任何位置的结果里都至少含有一个 0所以全是 0。这个例子把 0 的坑摆到了明面上但如果你用前面的前缀后缀法或原地解法跑一遍会发现根本不需要对 0 做任何特殊处理结果自然就是对的。这就是这套解法的优雅之处特殊输入不会破坏算法的统一流程。5.2 没有 0、单 0、多 0 三种情况如果面试官喜欢追问边界你可以把情况分成三类来回答数组里没有 0所有位置都能正常用前缀后缀算没有任何例外恰好一个 0只有 0 所在位置的结果是“其余所有非零元素乘积”其他位置的结果全部为 0至少两个 0所有位置的结果都为 0因为任一位置的其余元素里至少包含一个 0。从数学上看原因就是除法方案失败的同一个根源0 一旦参与乘法就会把整段乘积归零而且这种归零不可逆。前缀后缀方案不依赖逆推所以遇到 0 也完全正常这也是它比除法方案优雅的根本原因。5.3 如果面试官偏要你写除法版有些面试官会接着问“如果允许除法你会怎么写”这时候你心里要有一版预案。思路是先统计 0 的个数再分三种情况填充zero_count nums.count(0) if zero_count 1: return [0] * n if zero_count 1: idx nums.index(0) prod 1 for i, x in enumerate(nums): if i ! idx: prod * x ans [0] * n ans[idx] prod return ans total 1 for x in nums: total * x return [total // x for x in nums]把这版和前面的标准解法放在一起对比你会发现它更长、分支更多而且最核心的单 0 分支还是要额外扫一遍数组。这正好印证了题目为什么禁止除法没有除法你的代码反而更短、更不容易踩雷。5.4 负数会不会带来额外问题数组元素允许为负。前缀乘积和后缀乘积在负数参与下可正可负但乘法运算本身不关心符号连乘出来的正负号会自然保留最终 answer 也是正确的。唯一要注意的是零没有符号任何数乘 0 都是 0所以不要因为数组里存在负数就对“乘积是否为 0”产生迷惑。单 0 分支里非零位置乘积的正负号由负数个数决定比如 [-1, 1, -3, 3] 里两个负数乘积为正 9如果只有一个负数乘积就是负的。这些都在乘法规则内不需要额外处理。6. 前缀/后缀思想可以迁移到哪些题6.1 剑指 Offer 66构建乘积数组《剑指 Offer》第 66 题“构建乘积数组”和 LeetCode 238 是完全同一道题区别只是描述方式不同。你在很多刷题平台搜“productExceptSelf”或“构建乘积数组”会看到一堆变体。刷完这一道等于同时覆盖了两本“教材”里的高频题性价比很高。我甚至见过一些同学把这道题的代码原封不动背下来然后去面试里默写看起来效果还行但一旦面试官追问“为什么 L[i] 乘的是 nums[i-1]”背题的人就容易露馅。所以建议还是把递推的来龙去脉搞清楚再上考场。6.2 接雨水同样靠左右两个数组LeetCode 42 接雨水是另一道经典的“左右扫描”题。对每根柱子它能接住的水量等于 min(左边最高柱子, 右边最高柱子) - 当前柱子高度。很多标准解法也是先从左到右记录每个位置左边的最高值再从右到左记录右边的最高值最后取两者较小值合并。你对比一下就会发现它的结构跟本题的 L 和 R 几乎如出一辙只是 L、R 存的信息从“乘积”换成了“最大高度”。一旦理解这种“一维数组上的左右预处理”套路这类题就不再需要死记硬背了因为你会主动去想“这个位置的结果是不是也可以拆成左边信息和右边信息”6.3 前缀和与前缀积是同一个家族前缀和的思想比前缀积更普及一维数组 nums定义 prefix[i] nums[0] 到 nums[i-1] 的和那任意区间 [l, r) 的和就能用 prefix[r] - prefix[l] 快速求出。本题的前缀积本来也能做类似查询用除法把区间积还原出来但 LeetCode 直接禁掉了除法于是我们只好用 L 和 R 两边逼近。同样地前缀最大值、后缀最小值这类“预先把每个位置左右两侧的信息存好”的办法在一堆看似不相关的题里反复出现。所以我常说刷题不要只盯着单题解法要总结模式这道题最值得带走的模式就是当某个位置的结果同时依赖它左右两侧的信息时左右两趟扫描往往是突破口。6.4 我自己的三个刷题习惯最后分享几个我刷这道题时沉淀下来的小习惯希望能帮你少走弯路。第一拿到题先拿 [1, 2, 3, 4] 手工推导一遍 L 和 R再写代码这样基本能避免下标错位问题推导过程也就一分钟。第二代码写完不要直接提交先用题目给的两个示例验证尤其第二个带 0 的示例能直接暴露和 0 相关的逻辑错误有条件的话再补一个全 0 的样例比如 [0, 0]确认结果是 [0, 0]。第三做空间优化时先别急着看题解给自己五分钟想“到底能不能少用一个数组”这个思考过程比背题解更有价值。我踩过不少次“拿到题就开写、写完错到怀疑人生”的坑后来发现都是因为没有先花一分钟把边界条件在纸上跑通。这道题本身不难真正难的是把前缀/后缀这种思维方式内化成你自己的东西然后迁移到下一道题上去。