力扣热题100做到第8期今天选的题是《除自身以外数组的乘积》。这道题表面看只是数组遍历实际上玩的是前缀积和后缀积的巧妙配合是面试高频题也是很多状态压缩类题目的入门模板。题目要求很简单给定整数数组 nums返回一个数组 answeranswer[i] 等于 nums 中除 nums[i] 之外其余元素的乘积并且明确禁止使用除法时间复杂度要求 O(n)。很多第一次做这道题的人第一反应都是先算总乘积再逐个除一下马上就会被题目条件卡住。如果数组里有 0除法思路直接崩即便没有 0面试官也可能继续追问“你能不用除法吗”。所以这道题的真正价值不在于会写一个循环而在于能不能想到从左右两个方向累积乘积最后再合到一起。这篇文章我会从最朴素的思路开始拆解给出三种 Python 实现再聊聊我实际调试时踩过的坑最后说说这种前缀/后缀思想能迁移到哪些其他题目。1. 先看清楚这道题卡的是“用除法”的直觉1.1 除法的两个致命缺陷如果题目允许用除法解法确实很简短def product_except_self_division(nums): total 1 for x in nums: total * x return [total // x for x in nums]但这条思路有两个致命缺陷。第一是除零问题当数组里有任何一个元素等于 0 时nums[i]为 0 的位置直接除零报错。有人会说那就先统计零的个数遇到有 0 的情况单独处理。没错这确实能修但代码要分情况讨论零的个数等于 0、等于 1、大于等于 2三种情况分别给答案。逻辑一下子复杂很多而且面试官追问起来很容易在边界条件上翻车。第二是题目本身明确禁止使用除法。限制条件不是摆设面试官想看到的正是你能否跳出除法思维找到更底层的信息组织方式。我在实际面试中见过不少候选人上来就报“先求总乘积再除以当前数”被提醒不能用除法之后当场卡住。问题不在于会不会除法而在于没有意识到“每个位置的答案由两部分独立信息组成”。1.2 更本质的考点信息如何跨元素流动那不用除法还能怎么算回到定义对于输出位置 ianswer[i]等于“左半部分所有元素的乘积”乘以“右半部分所有元素的乘积”。左半部分是nums[0]到nums[i-1]右半部分是nums[i1]到nums[n-1]。这两个部分互相独立分别只跟左侧和右侧有关。如果我能提前把所有位置左侧的乘积算出来再把所有位置右侧的乘积算出来最后对应位置一乘就是答案。这种“把结果拆成左右两个独立子问题”的思路在算法题里非常常见后面我要讲的接雨水、买股票最佳时机本质上都在用类似的状态累积思想。所以这道题表面考的是“不能用除法”实际考的是“如何用递推代替除法”。前缀积和后缀积就是为这个场景量身定做的工具。2. 前缀积与后缀积左右夹击拼答案2.1 前缀积的定义前缀积英文叫 prefix product。为了统一描述我定义prefix[i]表示nums从下标 0 到i-1所有元素的乘积也就是prefix[i] nums[0] * nums[1] * ... * nums[i-1]注意它不包含nums[i]自己。当i 0时左边一个元素都没有按照乘法单位元取值为 1。为什么要这么定义因为这样最方便answer[i]的前半部分直接等于prefix[i]不用做任何下标偏移。前缀积可以一趟循环递推得到for i in range(1, n): prefix[i] prefix[i - 1] * nums[i - 1]2.2 后缀积的定义后缀积英文叫 suffix product。同理定义suffix[i]表示从下标i1到末尾所有元素的乘积suffix[i] nums[i1] * nums[i2] * ... * nums[n-1]当i n-1时右边没有元素取值同样为 1。后缀积要从后往前递推for i in range(n - 2, -1, -1): suffix[i] suffix[i 1] * nums[i 1]两个数组都只需要 O(n) 时间非常轻量。2.3 为什么相乘就是答案有了prefix和suffix之后答案就是answer[i] prefix[i] * suffix[i]因为除自身以外所有元素恰好被nums[i]分成了左右两堆左边一堆的乘积是prefix[i]右边一堆的乘积是suffix[i]两者互不重叠乘起来正好缺掉了nums[i]。举个例子nums [1, 2, 3, 4]inums[i]前缀积 prefix[i]后缀积 suffix[i]answer[i]01123424241213*41212231*224834123616最终返回[24, 12, 8, 6]。手工验算一下answer[2]等于除nums[2]3以外所有元素乘积也就是 1×2×48结果一致。这个例子看起来简单但里面有个关键点prefix[i]和suffix[i]的边界值都取 1。很多人写前缀积时习惯把prefix长度设为 n1存“到当前位置为止的累积乘积”那样也能做但下标映射会绕一些。我建议直接用“不含当前位置”的定义后面代码写起来最顺手。3. Python 实现从两趟遍历到常数空间3.1 版本一显式左右数组这是最清晰、最不容易出错的写法也适合在面试一开始用来讲思路。先把两个辅助数组算好再合并答案。def product_except_self(nums): n len(nums) prefix [1] * n suffix [1] * n for i in range(1, n): prefix[i] prefix[i - 1] * nums[i - 1] for i in range(n - 2, -1, -1): suffix[i] suffix[i 1] * nums[i 1] return [prefix[i] * suffix[i] for i in range(n)]时间复杂度 O(n)额外空间 O(n)。这个版本的可读性最好面试中先抛出来能让面试官立刻知道你的思路是对的。唯一的槽点是用了两个额外数组空间上不够极致。3.2 版本二输出数组复用省掉一个数组观察一下上面的代码会发现prefix和suffix其实只是临时数据。我可以先把prefix直接写到最终输出的ans数组里然后从右往左遍历时用一个滚动变量right维护后缀积边遍历边乘进去。def product_except_self(nums): n len(nums) ans [1] * n # 第一趟ans[i] nums[0] * ... * nums[i-1] for i in range(1, n): ans[i] ans[i - 1] * nums[i - 1] # 第二趟从右往左right 维护 suffix right 1 for i in range(n - 1, -1, -1): ans[i] ans[i] * right right * nums[i] return ans这个版本里第一趟结束后ans[i]存的是前缀积。第二趟从最后一个位置开始right初始为 1对应suffix[n-1]的空乘积。然后每访问一个位置先让ans[i]乘上当前的right再更新right乘上nums[i]为下一个左侧位置准备新的后缀积。我刚开始写这个版本时差点把ans[i] ans[i] * right和right * nums[i]的顺序搞反。如果先更新right再乘那么nums[i]会被错误地包含进ans[i]结果就全错了。记住一个口诀先消费后更新。3.3 版本三终极优化是“不优化”很多人看到“常数空间”会觉得还要再省实际上 LeetCode 有一个默认约定输出数组不计入额外空间。所以版本二已经做到了 O(1) 额外空间版本三是多余的。但“多余”不等于没有意义。从算法理论上说这道题的时间复杂度下界就是 O(n)每个输出位置需要左侧和右侧两堆独立的乘积信息而这两堆信息不可能凭空从某个全局变量里推出来必须分别扫描数组两边才能得到。想再省时间基本不可能。面试时主动说出“这是我能在时间和空间上达到的最优解”比闷头写代码更有说服力。3.4 处理边界n 的取值LeetCode 原题对nums.length的约束通常是2 nums.length 10^5至少有两个元素所以大多数解答没有讨论长度为 1 的情况。不过想得更深一点是好事如果数组长度是 1那么“除自身以外”没有其他元素按乘法单位元返回值应该是[1]。上面的两个版本都能自然处理这个情况因为prefix[0] 1第二趟里right也是 1。数组为空的情况在 LeetCode 一般不会出现面试中也不会问。但是如果你在写工具函数最好先判断一下长度不然n - 2这种下标会变成负数循环行为会很怪。提示面试的时候如果面试官没有明确说“输出数组算不算额外空间”优先按“输出数组不计入”的行业惯例来同时口头确认一句避免理解偏差。4. 调试实录这些坑我帮你们踩过了4.1 常见错误速查表我刷这道题和帮别人 review 代码时见过很多次典型的错误。列一个速查表对照着排查会快很多。症状可能原因解决方法第一个元素输出错误prefix初始化为 0或者prefix[0]没按 1 初始化前缀积数组全部初始化成 1prefix[0]天然是空乘积最后一个元素输出错误第二趟遍历写成range(n - 1, -1, -1)时right的更新时机不对确认先乘right到ans[i]再执行right * nums[i]结果数组全是 0把ans初始化成[0] * n之后在 0 的位置上做乘法初始化成[1] * n因为乘法单位元是 1后缀积全部偏大/偏小倒序循环起点写错比如从n - 1开始但suffix[n-1]被赋成了nums[n-1]后缀数组的最后一个位置应该是 1不是nums[-1]数组长度是 1 时行为怪没有处理空乘积为 1 的情况用“不含当前元素”的定义自动得到[1]4.2 为什么不能用乘法交换律来“跳过”自身也有人想过取巧既然不能用除法可不可以先把左边的乘积乘到总乘积里再除以自身这本质上还是除法绕不开除零问题。还有人会想到模逆元那是在模运算领域才适用的技巧而且需要题目保证模数与元素互质这里完全不符合。更隐蔽的错误是有人想用total // (total // nums[i])之类的变形来“跳过”且不说除零当数字很大时total // nums[i]在 Python 的整数除法下可能失真吗其实在这里total是nums[i]乘以其他所有元素的乘积所以total // nums[i]的结果一定是准确的。但这只是数学巧合前提是total能被nums[i]整除一旦中间乘积超过语言整数范围还会溢出。没必要在这种歪路上浪费时间老老实实前缀/后缀才是正解。4.3 内存不是白省的版本二确实省了数组但代价是代码的直观性稍微下降。我个人的经验是笔试阶段用最清晰的双数组版本先把正确性保住面试白板讲解时先写双数组说明思路再问一句“输出数组算不算额外空间”如果对方说算再演变成版本二。不要一上来就炫技写原地版本万一在面试官面前卡住反而得不偿失。从工程角度看两趟遍历都只依赖相邻状态可以很方便地扩展到流式处理场景。如果数据源是分批到达的第一趟可以先算前缀第二趟配合后缀合算几乎不需要改动。这也是为什么我建议把这道题的代码多写几遍直到不需要思考就能写对。5. 这道题背后的“两方向状态”思想能迁移到哪5.1 和“买股票的最佳时机”的对照力扣热题 100 的 Python 刷题攻略里经常把《买股票的最佳时机》和《除自身以外数组的乘积》放在一起对比。买股票那题只需要维护一个“到目前为止的最小值”是一种单方向的前缀信息而这道题需要同时知道左右两侧的乘积所以需要两次扫描。思想是相通的但维度不同。具体来说买股票走一趟就能算完因为答案只依赖历史不依赖未来。而《除自身以外数组的乘积》里answer[i]同时依赖历史和未来所以必须从两个方向收集信息。如果看《接雨水》就会发现更明显每个位置能接多少水取决于左边最大高度和右边最大高度这不就是“左右前缀/后缀”吗只不过那里用的是最大值这里用的是乘积。5.2 迁移原则从左到右再从右到左我总结了一个很实用的迁移原则凡是“每个位置的结果同时依赖前缀状态和后缀状态”的题目都可以考虑用两个预处理数组或者一个数组加一个反向滚动变量。通用套路是第一趟从左到右把能代表“左侧影响”的信息递推出来第二趟从右到左用滚动变量维护“右侧影响”边遍历边跟左侧信息合并合并逻辑往往是乘法、加法或取最大值具体看题目。这个套路在动态规划、滑窗、前缀和问题里都有变体。比如“每个元素乘以前面所有元素的和减去后面所有元素的和”这类题目本质上就是同一套骨架。练会这道题相当于掌握了一套模板后续遇到类似题型能少很多摸索时间。6. 现场实战建议怎么在面试里稳稳拿下这题6.1 先给暴力解再给优化我见过太多候选人上来就写最优解结果被面试官追问“为什么这么想”时支支吾吾。更好的做法是先用 30 秒说清楚暴力解法——对每个位置分别求左边乘积和右边乘积时间复杂度 O(n^2)然后指出问题在于重复计算接着引出前缀积和后缀积。这样面试官能看出你具备“先算复杂度再优化”的工程习惯。我也推荐在讲思路时画一下例子尤其是nums [1, 2, 3, 4]。在纸上列出前缀积数组和后缀积数组再写出答案。这种可视化的解释比直接扔代码效果好得多。6.2 主动谈边界和溢出面试官往往会在你写完代码后追加几个问题比如“数组里有 0 怎么办”“注意溢出吗”。这时候主动出击“我的解法天然规避了除零问题因为每次只乘不除。”“题目保证所有前缀积和后缀积都在 32 位整数范围内所以用 Python 的 int 不会溢出如果换成其他语言要注意用 long。”“输出数组不算额外空间我这里是 O(1) 额外空间。”这几句话一出口面试官一般会觉得你考虑周全。尤其是“天然规避除零”这一点是除法方案无法做到的也是这道题考查的重点。6.3 我个人刷这道题的体会最后说点个人经验。我最初刷这道题时第一版用的也是除法思路被一个用例[0, 1]直接打回原形。后来看懂前缀积和后缀积之后又盯着版本二的顺序问题迷糊了很久。真正让我开窍的是意识到“去掉当前元素”这件事本质上不是一次除法能解决的而是把信息拆成左右两部分用递推提前算好。从那以后我遇到同时依赖左右两侧影响的题都会条件反射地想能不能维护一个前缀数组再加一个反向变量。这种思维方式比单纯记住这道题的代码要重要得多。如果你正在刷力扣热题 100建议把这道题和《买股票的最佳时机》《接雨水》放在一起做对比它们的异同肯定会比单刷这一道题收获更大。
