力扣热题100刷到第8期今天聊一道非常经典的数组题除自身以外数组的乘积。这道题在力扣的编号是238也是热题100里几乎必考的一道面试命中率相当高。题目描述特别短给你一个整数数组 nums返回数组 answer其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。听着简单但题目有两个硬性要求不能用除法并且要在 O(n) 时间内完成。我第一次刷这道题先想到总乘积除以当前元素一看要求直接傻眼想暴力双重循环算算规模又放弃了。后来真正吃透前缀积与后缀积这套配合才发现这道题的设计精妙之处而且这类思想能平移到很多数组题上。1. 题目拆解为什么暴力解和除法解都走不通1.1 先看懂题目到底要什么在动手写代码之前我建议先拿一个具体例子把题目完全走一遍。比如输入nums [1, 2, 3, 4]输出应该是[24, 12, 8, 6]逐个解释answer[0] 是除 nums[0] 以外所有元素乘积也就是 2*3*4 24answer[1] 是 1*3*4 12answer[2] 是 1*2*4 8answer[3] 是 1*2*3 6。这个示例很关键后续所有推导我都会拿它来验证每一步正确性。也许有读者会问这题看着不就是在算每个位置“缺了自己”的乘积吗确实如此。但难点在于如果你老老实实对每个位置单独算一遍复杂度会非常难看如果取巧把所有元素先乘起来再用除法又会掉进题目明确禁止的坑。所以这道题表面考的是数组操作实际考的是你有没有“利用已有信息避免重复计算”的优化意识这种意识在真实业务里也很重要比如报表里大量重复统计指标时聪明做法是先算汇总再按需取用而不是每个维度重新跑一遍全量数据。1.2 暴力解法正确但注定超时最直觉的写法就是一个双重循环。外层遍历每一个位置 i内层遍历所有位置 j跳过 i 本身把其余元素乘起来。代码如下def productExceptSelf(nums): n len(nums) answer [] for i in range(n): product 1 for j in range(n): if i ! j: product * nums[j] answer.append(product) return answer逻辑没有任何问题正确性满分。但我建议你心里估算一下复杂度外层 n 次内层 n 次总次数约 n 的平方。力扣的测试数据通常能到 10 的 5 次方级别10 的 5 次方的平方是 10 的 10 次方哪怕一次乘法只要 1 纳秒也要 10 秒以上必然超时。所以在刷题时看到“数组长度为 10 的 5 次方”这类规模暗示应该条件反射想到不能容忍 O(n²)。有些朋友可能会想能不能剪枝优化比如先排序但排序会破坏元素原来的位置关系答案是每个位置都要对应自己的“除自身之外乘积”排序后索引就对不上了。所以暴力解只能在理解题意时用不能作为最终答案。1.3 除法解法看着很香实则是坑另一个很容易想到的思路是先把整个数组的元素全部乘起来得到一个总乘积 total然后对每个位置 ianswer[i] total 除以 nums[i]。伪代码如下total 1 for num in nums: total * num answer [] for num in nums: answer.append(total // num)这段代码跑在 nums [1, 2, 3, 4] 上结果确实能得到 [24, 12, 8, 6]所以很多人第一反应都是它。但题目特别强调不能用除法为什么因为除法方案有致命问题只要数组里存在一个 0total 就是 0而某个位置的 nums[i] 可能是 0此时 0 除以 0 是没有意义的更麻烦的是当 total 0 且 nums[i] 0 时你无法从 total / nums[i] 推出“除自身以外”的乘积因为那部分信息在这个除法操作中已经丢失了。举个例子nums [0, 1, 2]正确答案是 [2, 0, 0]但用除法算total 0第一个位置 0 / 0 直接报错就算强行约掉也拿不到 2 这个结果。其实更根本的问题在于除法会丢失“其他元素乘积”这个独立信息。前缀积与后缀积之所以巧妙正是因为它只用乘法组合信息从根源上避开了零和溢出带来的各种边界情况。2. 前缀积与后缀积整套思路的核心推导2.1 从左往右累积前缀积的构造要理解这道题的正解先记住一个核心结论answer[i] 只依赖两样东西——位置 i 左边所有元素的乘积和位置 i 右边所有元素的乘积。左右两边互不干扰分别算好再相乘就能得到“除自身以外”的乘积。先看左边。我定义 prefix[i] 表示“从 nums[0] 一直乘到 nums[i-1]”的结果也就是位置 i 左边所有元素的乘积。注意这里的关键点prefix[i] 不包含 nums[i] 自己。那么递推关系非常自然prefix[0] 1 # 位置0左边没有元素空乘积定义为1 prefix[i] prefix[i-1] * nums[i-1] # 左边多乘一个元素为什么 prefix[0] 是 1 而不是 0这跟乘法单位元有关。任何数乘以 1 都等于它自己所以“空乘积”用 1 表示能保证递推公式在边界处依然成立。如果用 0那么后面所有前缀积都会被“污染”成 0整个算法直接报废。以 nums [1, 2, 3, 4] 为例从左到右扫描一遍prefix[0] 1 prefix[1] prefix[0] * nums[0] 1 * 1 1 prefix[2] prefix[1] * nums[1] 1 * 2 2 prefix[3] prefix[2] * nums[2] 2 * 3 6得到 prefix [1, 1, 2, 6]。可以对照着验证prefix[3] 6 确实是 1*2*3也就是位置 3 左边所有元素的乘积。2.2 从右往左累积后缀积的构造后缀积跟前缀积完全对称。我定义 suffix[i] 表示“从 nums[i1] 一直乘到 nums[n-1]”的结果也就是位置 i 右边所有元素的乘积。同样地最右边的位置 n-1 右边没有元素所以suffix[n-1] 1 suffix[i] suffix[i1] * nums[i1] # 右边多乘一个元素再从右往左把 nums [1, 2, 3, 4] 扫一遍suffix[3] 1 suffix[2] suffix[3] * nums[3] 1 * 4 4 suffix[1] suffix[2] * nums[2] 4 * 3 12 suffix[0] suffix[1] * nums[1] 12 * 2 24得到 suffix [24, 12, 4, 1]。注意这里 suffix[0] 24恰好就是除了 nums[0] 之外所有元素的乘积跟题目第一项的答案一致说明思路方向是对的。你可以用生活场景来理解这两步想象一条流水线上有四个工人每个人手里拿着一张卡片卡片上写着“左侧所有工人的编号乘积”。这是前缀积。另外再发一张卡片写着“右侧所有工人的编号乘积”。这是后缀积。每个工人把自己手里的两张卡片相乘就是除自己之外所有工人的编号乘积。整个过程不需要任何一个人去问全队其他人的编号只需要两次集体传递信息就齐了。2.3 把两边乘起来核心公式的诞生有了前缀积和后缀积答案几乎是一行公式的事answer[i] prefix[i] * suffix[i]为什么因为“除 nums[i] 以外所有元素的乘积”正好可以拆成“nums[i] 左边的所有元素乘积”乘以“nums[i] 右边的所有元素乘积”。左边部分跟右边部分互不重叠也不会包含 nums[i] 自己完美符合题目要求。用 nums [1, 2, 3, 4] 验证answer[0] prefix[0] * suffix[0] 1 * 24 24 answer[1] prefix[1] * suffix[1] 1 * 12 12 answer[2] prefix[2] * suffix[2] 2 * 4 8 answer[3] prefix[3] * suffix[3] 6 * 1 6跟最开始手算的结果完全一致。这套方案全程只用乘法时间复杂度是两次线性扫描 O(n)空间复杂度取决于你是否额外开了两个数组但如果只用一个输出数组复用还能做到 O(1) 额外空间。这就是力扣官方题解里说的“前缀积 后缀积”的完整思想。3. Python 实现从直观写法到空间优化3.1 第一版双数组思路最直白如果你是第一次见这道题我建议先写出最易读的版本不要急着优化。第一版代码就是按照前缀积和后缀积两个数组各扫一遍最后相乘def productExceptSelf(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] answer [prefix[i] * suffix[i] for i in range(n)] return answer这里有两个循环边界特别容易写错。第一个循环从 1 开始因为 prefix[0] 已经初始化为 1不需要也不能再用公式去覆盖第二个循环从 n-2 开始同理因为 suffix[n-1] 已经是 1。很多新手会把第二个循环写成 range(n-1, -1, -1)然后 suffix[i] suffix[i1] * nums[i1] 在 i n-1 时会越界直接报错。这种边界问题在笔试手写代码时很常见我通常会在写完循环后立刻做一次“首尾边界检查”确保索引不会出界。这一版的时间复杂度是 O(n)空间复杂度是 O(n)因为额外开了两个长度 n 的数组。如果面试官不追问这个版本其实已经满足题目最基本的 O(n) 时间要求。但热题100这道题几乎一定会被追问能不能把额外空间降到 O(1)3.2 第二版输出数组复用空间降为 O(1)空间优化的关键思路只有一句话我不需要真的开两个独立数组我可以用输出数组 answer 先存前缀积再用一个变量存后缀积边扫边乘。这样就把额外空间从 O(n) 压缩到 O(1)。具体做法分两步。第一步从左往右扫描把前缀积直接写进 answerdef productExceptSelf(nums): n len(nums) answer [1] * n for i in range(1, n): answer[i] answer[i - 1] * nums[i - 1]这样跑完之后answer [1, 1, 2, 6]这就是每个位置的前缀积。第二步从右往左扫描用一个变量 right 来维护当前位置右侧所有元素的乘积。注意顺序很关键必须先让 answer[i] 乘上当前的 right再把 nums[i] 乘进 right供下一次循环使用。代码如下right 1 for i in range(n - 1, -1, -1): answer[i] * right right * nums[i] return answer整个过程走一遍初始 right 1。i 3 时answer[3] 乘 1 仍等于 6然后 right 1*4 4i 2 时answer[2] 乘 4 得到 8然后 right 4*3 12i 1 时answer[1] 乘 12 得到 12然后 right 12*2 24i 0 时answer[0] 乘 24 得到 24。最终 answer [24, 12, 8, 6]完全正确。这个版本的简洁之处在于answer 同时扮演了“前缀积存储数组”和“最终答案数组”两个角色后缀积则完全靠一个整数变量滚动维护。面试官看到这个版本基本就会点头了。LeetCode 的 Follow Up 里也明确写了输出数组不计入空间复杂度所以这个方案在官方定义下就是 O(1) 额外空间。3.3 边界与细节初始化、遍历方向、变量更新时机很多时候算法思路没错但代码在边界或细节上翻车。我把这题最容易出问题的三个细节单独拎出来说。第一个细节是初始化。前缀积和后缀积的边界位置都必须初始化为 1不能是 0也不能是其他数。原因在前面说过1 是乘法的单位元空集乘积定义为 1这样递推公式才能在边界处无缝衔接。如果初始化成 0那整个乘积链就直接断掉了。第二个细节是遍历方向。前缀积必须从左往右后缀积必须从右往左。这个方向反了信息传递就会乱。前缀积的递推依赖前面的结果后缀积依赖后面的结果所以方向是锁死的。第三个细节是反向遍历时变量更新的先后顺序。代码里的顺序是“先乘到 answer 上再更新 right”。如果把顺序颠倒成“先 right * nums[i]再 answer[i] * right”那么对于 i n-1 这个位置right 会先乘上 nums[n-1]也就是把当前元素本身也乘进去了答案立刻变错。我见过很多人在这一步翻车排查很久才发现是更新顺序问题。你可以这么记right 代表的是“位置 i 右边所有元素的积”所以在处理 i 之前right 绝对不能包含 nums[i] 自己。4. 常见问题与避坑实录4.1 数组里有 0要不要特殊处理不少读者一看到除法被禁止就猜测是不是需要专门处理 0。其实不需要。前缀积与后缀积方案全程只用乘法0 的处理完全遵循正常乘法规则。举个例子nums [0, 1, 2, 3]前缀积 prefix [1, 0, 0, 0] 后缀积 suffix [6, 6, 3, 1] answer [6, 0, 0, 0]逐个验证answer[0] 1*2*3 6answer[1] 0*2*3 0answer[2] 0*1*3 0answer[3] 0*1*2 0。结果完全正确。再极端一点如果数组里有两个 0比如 nums [0, 1, 0, 3]那么除了第一个 0 的位置其他每个位置都至少包含一个 0答案全部是 0。前缀积和后缀积也能自动算出来不需要任何 if 分支。这就是这个解法的鲁棒性你不需要为 0 写任何特殊逻辑。4.2 输出数组到底算不算额外空间这是一个面试中很容易被抓住的细节。很多人在第一版双数组解法里说“空间复杂度 O(n)”面试官会追问能不能优化当你说出第二版后面试官可能又问你这个还是用了 answer 数组算不算额外空间这类问题的标准答案写得很清楚LeetCode 238 的 Follow Up 明确说明输出数组不计入额外空间。所以第二版在官方定义下就是 O(1) 额外空间。至于平时讨论时你可以说“如果不把输出数组计入额外空间是 O(1)如果计入就是 O(n)”。这样回答既准确又不卑不亢。4.3 单循环左右同时推进为什么容易写错我在刷题时见过不少脑洞大开的写法最典型的一种是试图在一个 for 循环里同时从左和从右推进省成一次扫描。比如这种片段res [1] * n left 1 right 1 for i in range(n): j n - 1 - i res[i] * left res[j] * right left * nums[i] right * nums[j]这个写法我亲自试过结果会错。原因在于对于左边的位置 i它需要右侧所有元素的后缀积但这个后缀积要等右边的信息全部扫描完才知道对于右边的位置 j它的前缀积同理。单循环同时推进时左右两侧的信息在“相遇”之前都没有完整覆盖到对方区域因此会产生信息缺失。我自己实验了多种变量更新顺序最终确认这题不适合在 O(1) 额外空间下硬写成单循环。不是代码技巧不够而是信息本身就分两个方向传递分成两次扫描是最自然、最稳的。与其为了炫技写一个容易错的版本不如老老实实写两个循环。4.4 高频排查点速查表把常见的报错和逻辑错误整理成一张速查表方便你自查症状可能原因处理办法结果全是 0前缀或后缀数组初始化为 0改为初始化为 1某个位置结果偏大或偏小正向或反向循环边界写错正向从 1 开始反向从 n-2 开始反向扫描出现越界range(n-1, -1, -1) 内访问了 nums[i1]改用后缀数组从 n-2 开始或用 right 变量答案包含自身元素反向更新时先更新 right 再乘到 answer先乘再更新 right空间复杂度被认为不达标额外开了两个数组用 answer 数组存前缀积变量维护后缀积总想用除法忽略题目禁止除法要求回到前缀积与后缀积思路这张表是我在实际写代码过程中总结出来的。刷题时遇到测试过不了先别急着怀疑算法整体按表逐项排除通常很快就能定位问题。5. 同类问题延伸与面试考察角度5.1 一个思想打穿多道题前缀积与后缀积不只是这一道题的解法它背后是一个更通用的思想当某个位置的答案由“左侧信息”和“右侧信息”共同决定就可以分别扫描两次把两侧信息都算出来再合并。拿这个思想去看热题100里的几道经典题会有豁然开朗的感觉。先看接雨水这道题力扣42。它要求计算每个位置能接多少水而每个位置的接水量取决于它左右两侧最高柱子的较小值。典型解法就是从左往右扫描一遍维护一个 left_max再从右往左扫描一遍维护一个 right_max然后每个位置取 min(left_max, right_max) 减去当前高度。这个模式跟今天的题目几乎一模一样左右两遍扫描各维护一个累积状态最后合成答案。再看买卖股票的最佳时机力扣121。它要求一次交易获得最大利润经典解法是遍历股票价格同时维护一个“到目前为止的最低买入价”用当前价格减去最低价更新最大利润。这虽然不是严格的前缀后缀但同样是一边遍历一边累积历史信息跟 prefix 的累积思路是同源的。热题100里还有乘积最大子数组力扣152需要同时维护“以当前位置结尾的最大乘积”和“最小乘积”因为负数乘负数会变正数它把“状态累积”和“正负符号”结合得更深。把这些题放在一起刷你就能自然体会到很多数组难题并不是真有多难只是少了一个“分开看左右两侧”的视角。5.2 面试中的追问方向与应对如果面试官让你手写这道题通常会有几条追问路线。第一条路线是问复杂度先让你实现暴力解再问能不能 O(n)最后问能不能 O(1) 额外空间。第二条路线是问边界数组里有 0 怎么办有多个 0 怎么办能不能不用除法。第三条路线是问变形比如把“乘积”换成“累加和”让你写一个“除自身以外数组的和”。其实思路完全一样把乘法换成加法即可前缀和和后缀和配合就能解决。这些追问都是在考察你是不是真的理解了前缀积与后缀积的本质而不是背了模板。除了刷热题100的题目我还建议你养成一个习惯每道题做完之后写下这道题最核心的一个技巧然后用这个技巧去关联同类的两三道题。比如今天这道题的核心技巧是“左右两侧信息分开累积”那么你就可以关联接雨水、买卖股票、前缀和这三类题。这样刷下来你的知识不是一道题一道题的孤岛而是一张互相连接的网络面试时也更容易举一反三。从我个人刷题经验来看热题100的价值不在于刷了多少遍而在于你能不能把每一道题背后的思想迁移出去。这道“除自身以外数组的乘积”难度不算高但前后缀配合的思想很典型值得反复咀嚼。如果你能不看任何题解自己写完 O(1) 空间版本并把变量更新的时机讲清楚这道题基本就算彻底掌握了。最后再分享一个我的小习惯刷这种左右扫描的题我会专门用一个表格记录每个位置每一轮的状态比如 prefix、suffix、right 三个变量在每轮循环后的值这样一旦结果不对一眼就能看出是第几轮出现问题。磨刀不误砍柴工这个习惯帮我省了不少调试时间。
