我第一次认真琢磨前缀后缀这个套路是因为一道流传很广的算法题给定一个整数数组要求返回一个新数组新数组的每个位置是原数组除该位置外的所有元素乘积。也就是经典的除了自身之外的数组乘积Product of Array Except Self。题目乍看是小学乘法真正动手才发现它同时禁用了除法和 O(n²) 的暴力扫描逼着你把结果拆成左边乘积 × 右边乘积两步走。这篇文章不打算只贴一份标准答案而是把完整的思考链条走一遍为什么暴力法不行、前缀积和后缀积怎么构造、空间怎么压缩、边界条件怎么处理以及这个范式在真实编码里还能用在哪儿。不管你是准备面试还是写业务代码时正好遇到每个位置都要用两侧上下文信息的需求这篇都能给你一套可以直接落地的思路。1. 题目本身很简单难在两条约束同时成立1.1 需求拆解answer[i] 是数组去掉第 i 个元素后的总乘积输入数组 nums长度记为 n输出数组 answer长度同样为 n并且满足answer[i] nums[0] × ... × nums[i-1] × nums[i1] × ... × nums[n-1]翻译成人话第 i 个位置的结果等于原数组里除了 nums[i] 自己以外所有元素的乘积。举个例子nums [1,2,3,4] 时answer[0] 2×3×4 24answer[1] 1×3×4 12answer[2] 1×2×4 8answer[3] 1×2×3 6所以期望输出 [24, 12, 8, 6]。题目本身只有一句话但它埋了两个硬性约束不能用除法时间复杂度必须是 O(n)。更严格一点的版本还会追加一问能否只使用 O(1) 的额外空间这三条叠在一起才是这道题真正的全貌。多数人在面试时翻车不是不会写代码而是没有意识到这些约束是在引导一种特定的思维路径。1.2 禁除法 线性时间约束背后的出题意图先看除法。如果允许除法第一反应是求出整个数组的总乘积 total然后让 answer[i] total / nums[i]。这确实是 O(n) 的方案代码短得离谱几行就能写完。但为什么所有标准题解都拒绝它理由有两个一个很具体一个很根本。第一个理由很具体零。只要数组里出现一个 0total 就是 0任何 answer[i] 0 / 0 或者 非零数 / 0 都无法计算直接崩盘。你当然可以引入分情况讨论把0 的个数分成零个、一个、多个三种情况分别处理代码立刻变脏而且恰恰暴露了你根本没理解这道题想要考察什么。第二个理由很根本题目设计者把除法禁掉就是在告诉你——必须在乘法层面构造答案。乘法层面唯一自然的分解就是把除自己之外所有元素的乘积看作左边所有元素的乘积 × 右边所有元素的乘积。这个分解一旦想通前缀积和后缀积就是水到渠成的事。我在模拟面试时常跟 A 同学讲看到禁止除法先别急着想怎么绕过而是停下来想一想题目是不是在暗示一种分而治之的结构。再说 O(n) 这个约束。O(n²) 的双重循环能算出正确答案但数据量一大就不可行。这里其实藏着一个所有性能优化问题都通用的动机重复计算。每个位置的答案都要重新乘一遍所有其他元素而这些乘积之间高度重叠。优化思路就是四个字——算一次、存下来、反复用把每次重新计算变成查表复用。2. 先走两条弯路双重循环和除法方案各自翻车在哪里2.1 暴力双重循环逻辑正确但复杂度一眼超时先写最自然的暴力解法def product_except_self_naive(nums): n len(nums) res [] for i in range(n): prod 1 for j in range(n): if i ! j: prod * nums[j] res.append(prod) return res这段代码没有任何逻辑漏洞拿 [1,2,3,4] 测试照样返回 [24, 12, 8, 6]。问题出在复杂度外层 n 次内层 n 次总体 O(n²)。n 10^4 时大约要执行 10^8 次乘法肉眼可见地卡顿n 10^5 时直接不可接受。嘴上说慢没有体感我建议你在本地跑一下对比实验随机生成十万长度的数组先用暴力法跑测时间再用后面的前缀/后缀版本跑对比会非常直观。面试里不会真的让你跑数据但性能意识是基本功至少你要能一口气说清楚两个循环嵌套、每层都是 n 规模、所以是平方级这个分析过程。2.2 除法方案代码最短零元素一来就崩除法方案长这样def product_except_self_division(nums): total 1 for x in nums: total * x return [total // x for x in nums]如果输入全是正数、没有零这段代码是完美的一次遍历求总乘积再一次遍历逐个除以自身。但现实数据不会那么乖巧只要出现一个 0程序直接崩。就算你用 try/except 兜住异常返回的结果也完全没意义。再退一步手动处理零元素就要分成三种情况讨论零的个数为 0用 total // nums[i]一切正常。零的个数为 1只有零所在位置的答案是所有非零元素的乘积其余位置全为 0。零的个数 ≥ 2所有位置答案全为 0。代码至少多出三个分支每多一个分支就多一个出错可能。到这里你应该能感觉到这道题禁用除法不是在为难你而是在帮你避开一个更深的坑——把注意力引导到真正通用的前缀/后缀范式上。2.3 四种方案的横向对比方案时间复杂度空间复杂度能否处理零是否符合题目要求暴力双重循环O(n²)O(1)能不符合超时总乘积除法O(n)O(1)不能不符合禁除法前缀后缀辅助数组O(n)O(n)能符合前缀后缀原地压缩O(n)O(1)能符合满足进阶这个表格在面试时可以直接画给面试官看短短几行就能证明你不仅会写代码还清楚自己的解法在复杂度层面处于什么位置。3. 前缀积与后缀积把答案拆成左乘右两次扫描解决3.1 关键洞察排除自身恰好意味着左右两侧互不相干回到定义answer[i] 是左边所有元素乘积 × 右边所有元素乘积。因为除了 nums[i] 自己所有元素恰好分成左侧一组和右侧一组两组之间没有重叠。形式化地写left[i] nums[0] × ... × nums[i-1]左边累计乘积right[i] nums[i1] × ... × nums[n-1]右边累计乘积answer[i] left[i] × right[i]这里要特别注意边界约定left[0] 1因为第一个元素左边没有元素空集的乘积约定为 1right[n-1] 1同理。这个空集乘积为 1的约定是整个推导的地基也是很多人第一次写时容易忽略的地方。它不是随便定的而是为了保证递推式在边界位置依然成立。3.2 从左到右构造前缀积的递推以及一个常见下标错误前缀积的递推关系非常自然要得到 left[i]只需要知道 left[i-1]再乘上 nums[i-1]因为到 i-1 为止的累计乘积再乘上第 i-1 个元素恰好就是到 i 为止的累计乘积。n len(nums) left [1] * n for i in range(1, n): left[i] left[i-1] * nums[i-1]拿 [1,2,3,4] 走一遍left 初始为 [1,1,1,1]i1 时 left[1] 1×1 1i2 时 left[2] 1×2 2i3 时 left[3] 2×3 6最终 left [1,1,2,6]。这里有一个非常高发的下标错误新手容易把公式写成 left[i] left[i-1] * nums[i]这样语义就变成了截止到 i 的累计乘积包含了 nums[i] 自己与需求完全相反。记住一条判断标准left[i] 存的是当前格子左侧的信息不应该包含当前格子的元素。写完代码后可以用 left[1] 是否等于 nums[0] 来快速自检如果不等一定错了。3.3 从右到左构造后缀积逐位合并得到答案后缀积完全对称right[n-1] 1递推方向从数组尾部往头部走。right[i] right[i1] × nums[i1]意思是到 i 右侧的累计乘积等于i1 右侧的累计乘积再乘上 nums[i1]。right [1] * n for i in range(n-2, -1, -1): right[i] right[i1] * nums[i1]同样用 [1,2,3,4] 走一遍right 初始 [1,1,1,1]i2 时 right[2] 1×4 4i1 时 right[1] 4×3 12i0 时 right[0] 12×2 24最终 right [24,12,4,1]。最后一步合并对应位相乘answer [left[i] * right[i] for i in range(n)]left 是 [1,1,2,6]right 是 [24,12,4,1]逐位相乘得到 [24,12,8,6]与预期完全一致。到这一步标准的 O(n) 时间、O(n) 空间解法就完整了。3.4 为什么必须扫两遍而不能一遍走完可能是整篇文章最值得想清楚的问题能不能只从左到右扫一遍把答案全部算出来答案是不能。因为当扫描到位置 i 时你手上只有左侧累计的信息右侧的信息还完全未知必须等扫描走到数组末尾之后才有办法回头处理右侧。所以前缀/后缀类解法的模板永远是正着扫一遍收集左侧信息反着扫一遍收集右侧信息最后合并。这个两次扫描的骨架比这道题本身值钱多了。你会在后面的接雨水、前缀和等一系列题目里反复见到它它们共享同一个抽象一个位置的最终答案同时依赖左右两侧的某种累计状态。4. 空间压缩把辅助数组省到只剩一个滚动变量4.1 第一轮把答案数组当前缀积仓库题目进阶要求 O(1) 额外空间。前面的解法用了 left 和 right 两个长度为 n 的数组这显然不是 O(1)。优化的切入点是返回的 answer 数组最终反正是要给出空间的它本身就是长度为 n 的存储区为什么不在运算过程中先拿它来装前缀积这样 left 数组就可以直接省掉。第一轮扫描把前缀积写进 answeranswer [1] * n for i in range(1, n): answer[i] answer[i-1] * nums[i-1]第一轮结束后answer 里面存的就是原来 left 数组的内容相当于借用了这块存储区。此时 answer 的值是 [1,1,2,6]跟上一节 left 一致。4.2 第二轮用 right 变量边乘边写完成后缀合并后缀积没有再借数组而是改用一个滚动变量 right 边扫边更新。right 的语义是在从右往左的扫描过程中已经扫过的元素也就是当前元素右边的所有元素的累计乘积。初始 right 1因为最右边元素的右边没有元素。每走到位置 i执行两件事先 answer[i] * right把右侧累计信息乘进已有的前缀积再把 nums[i] 乘进 right为处理更左边的位置做准备。right 1 for i in range(n-1, -1, -1): answer[i] * right right * nums[i]完整代码如下def product_except_self(nums): n len(nums) answer [1] * n # 第一轮存前缀积 for i in range(1, n): answer[i] answer[i-1] * nums[i-1] # 第二轮乘后缀积 right 1 for i in range(n-1, -1, -1): answer[i] * right right * nums[i] return answer对照 [1,2,3,4] 再验证一遍第一轮后 answer [1,1,2,6]。第二轮i3answer[3] 6×1 6right 1×4 4i2answer[2] 2×4 8right 4×3 12i1answer[1] 1×12 12right 12×2 24i0answer[0] 1×24 24right 24×1 24最终结果 [24,12,8,6]正确。注意最后一次更新 right 虽然已经没有更左边的位置需要它了但这样写能让循环逻辑保持统一不影响正确性。4.3 顺序、边界、初始值三个最容易写错的细节这部分是我带人写这道题时反复踩坑的总结每条都很小但每条都能让程序跑出完全错误的结果。第一更新顺序必须是先乘 answer再更新 right。如果顺序反过来等于把 nums[i] 也乘进了当前格子的答案把除自身之外错误地变成包含自身。一个简单记忆方法answer[i] 需要的是右边的乘积nums[i] 属于左边范围不能混进 right。第二循环边界。第一轮从 i1 到 n-1第二轮从 in-1 递减到 0两个范围都必须完整覆盖。漏掉最后一个位置通常会导致边界元素答案错误而且这种错误在短数组上非常隐蔽。第三初始值。answer 数组和 right 变量的初始值都是 1乘法单位元。如果你顺手写成 [0] * n所有乘积都会被清零right 写成 0第二轮全部变 0。这类错误在键盘上很容易发生尤其是在你刚写完别的数组题之后。提示写好之后先用 [1,2,3,4] 手动推一遍再用 [1,0,3,4] 和 [1,0,0,4] 各测一次。这三个用例能覆盖绝大多数乘积类边界。5. 边界情况与实测翻车记录零、短数组、溢出5.1 含零输入的结果形态一个零和多个零完全不同前缀/后缀方案本身不怕 0不会有除零问题但如果你不理解含零输入的结果形态写自测用例时容易懵。结论分三种。没有零时结果是一般形态可能有正有负。恰好一个零时只有零所在位置的答案是所有非零元素的乘积其余位置全是 0。两个或更多零时答案数组全体为 0。这个结论的背后是同一个道理排除一个位置后剩下的元素里只要还有一个 0乘积就是 0。我第一次刷这道题时就是用含一个 0和含两个 0两种输入来自测跑通之后对算法的信心瞬间就建立起来了。你也可以用这个结论反过来检查如果输出里出现了不该出现的非零值说明滚动的 right 变量把自身乘进去了。5.2 单元素与空数组的防御性处理题目通常约定 n ≥ 2但如果你把这段逻辑封装成通用工具函数就要考虑 n 1 的场景。对于数组 [x]除了自身之外没有别的元素答案按约定是 [1]。用前缀/后缀逻辑推导也成立第一轮保持 [1] 不变第二轮 right 一直为 1answer[0] 1没有问题。空数组直接返回空数组即可。这些边界写在函数开头当防御性判断成本极低但收益不小。实际项目里工具函数被别处调用时没有人会替你想好数组会不会只有一个元素这种问题自己处理好才是负责任的写法。5.3 大数溢出不同语言的差异很大甚至需要换思路这道题的乘积可能非常大。比如 nums [100000] × 6总乘积是 10^3032 位 int 直接爆掉。LeetCode 的测试用例通常保证结果在合理范围内但真实业务不保证。Python 的整数没有上限天然安全C、Java、Go 里就要考虑用 long 或 long long再大就得用大数库。我自己在业务代码里处理过类似的除自身外乘积需求当时数据是十几个 10^4 量级的特征值乘积轻松超过 64 位。最后的解法不是硬扛大数而是转换思路把乘积转化为对数下的求和再用指数还原牺牲一点精度换取速度和空间。负数场景也要留意整体符号取决于负数的奇偶个数最好单独统计而不是靠中间值临时判断。6. 这个套路不止一道题前缀/后缀思想还能怎么用6.1 接雨水同一种骨架只是累积信息从乘积变成了最大值前缀/后缀思想最常见的延伸题是接雨水。每个柱子能接多少水等于左右两侧最高柱子的较小值减去当前柱子高度。做法从左往右扫一遍记录前缀最大值再从右往左扫一遍记录后缀最大值然后逐位置取较小值再减。这跟在数组乘积里的结构完全一致正扫、反扫、合并。差别只在于累积的信息从乘积变成了最大值。如果你把这道题练透了接雨水基本就是复制粘贴级别的改动。6.2 前缀和更常见的是加法版亲戚前缀和可能是前缀思想最广泛的应用。定义 prefix[i] 为前 i 个元素之和那么任意区间 [l, r) 的和等于 prefix[r] - prefix[l]O(1) 查询。股票买卖的最佳时机用前缀最小值二维矩阵的子矩阵和用二维前缀和。它的本质和前缀积一模一样把到当前位置为止的累计信息预存下来后续需要区间信息时直接查表。把前缀积、前缀和、前缀最大/最小值放在一起看你会抽象出一个特别有用的框架如果题目要求每个位置都依赖左边某个变换的结果和右边某个变换的结果十有八九可以用前缀/后缀两次扫描解决。拿到题先问自己两个问题左侧要累积什么状态右侧要累积什么状态定义清楚了代码结构自然就出来了。6.3 真实项目中的两个应用片段这个范式绝不是面试专属。我在做用户行为序列的特征工程时想构造某用户在时间点 t 之前的行为序列乘积收益和之后的行为序列乘积收益用来衡量当前行为在整体序列中的相对位置——这不就是这道题的前缀积加后缀积吗还有一次是在推荐系统的上下文特征里需要计算某个候选商品前面所有商品的加权累计和与后面所有商品的加权累计和同样两轮扫描搞定。所以刷题刷出来的抽象能力是真的可以迁移到生产代码里的。这也是我为什么坚持认为像除了自身之外的数组乘积这种题值得花时间把每一步推导都吃透。最后分享一个我自己多年的习惯遇到需要优化复杂度的题目先写最朴素的正确版本再写带辅助数组的版本最后再压缩空间。三步走看似费时间实际上每一版都可以独立验证正确性一旦压缩空间的版本出了 bug回头对比中间版本立刻能定位是逻辑问题还是边界问题。这道题我前前后后写过不下十遍踩过的坑基本集中在初始化、边界、更新顺序这三件事上。如果你也在准备面试建议把这几个点提前背熟并且养成提交前用三个用例自测的习惯纯正数、含一个零、含多个零。这三个用例一过这道题基本就稳了。至于正扫 反扫 合并这个句式我建议你不仅背下来还要能说清楚为什么必须扫两次——能讲明白这一句面试官对你的评价通常不会差。 
长河君 · 2026/10/22 16:41:52 · 阅读 1.2k 前缀积与后缀积：解决“除自身外数组乘积”的两遍扫描范式
我第一次认真琢磨前缀后缀这个套路是因为一道流传很广的算法题给定一个整数数组要求返回一个新数组新数组的每个位置是原数组除该位置外的所有元素乘积。也就是经典的除了自身之外的数组乘积Product of Array Except Self。题目乍看是小学乘法真正动手才发现它同时禁用了除法和 O(n²) 的暴力扫描逼着你把结果拆成左边乘积 × 右边乘积两步走。这篇文章不打算只贴一份标准答案而是把完整的思考链条走一遍为什么暴力法不行、前缀积和后缀积怎么构造、空间怎么压缩、边界条件怎么处理以及这个范式在真实编码里还能用在哪儿。不管你是准备面试还是写业务代码时正好遇到每个位置都要用两侧上下文信息的需求这篇都能给你一套可以直接落地的思路。1. 题目本身很简单难在两条约束同时成立1.1 需求拆解answer[i] 是数组去掉第 i 个元素后的总乘积输入数组 nums长度记为 n输出数组 answer长度同样为 n并且满足answer[i] nums[0] × ... × nums[i-1] × nums[i1] × ... × nums[n-1]翻译成人话第 i 个位置的结果等于原数组里除了 nums[i] 自己以外所有元素的乘积。举个例子nums [1,2,3,4] 时answer[0] 2×3×4 24answer[1] 1×3×4 12answer[2] 1×2×4 8answer[3] 1×2×3 6所以期望输出 [24, 12, 8, 6]。题目本身只有一句话但它埋了两个硬性约束不能用除法时间复杂度必须是 O(n)。更严格一点的版本还会追加一问能否只使用 O(1) 的额外空间这三条叠在一起才是这道题真正的全貌。多数人在面试时翻车不是不会写代码而是没有意识到这些约束是在引导一种特定的思维路径。1.2 禁除法 线性时间约束背后的出题意图先看除法。如果允许除法第一反应是求出整个数组的总乘积 total然后让 answer[i] total / nums[i]。这确实是 O(n) 的方案代码短得离谱几行就能写完。但为什么所有标准题解都拒绝它理由有两个一个很具体一个很根本。第一个理由很具体零。只要数组里出现一个 0total 就是 0任何 answer[i] 0 / 0 或者 非零数 / 0 都无法计算直接崩盘。你当然可以引入分情况讨论把0 的个数分成零个、一个、多个三种情况分别处理代码立刻变脏而且恰恰暴露了你根本没理解这道题想要考察什么。第二个理由很根本题目设计者把除法禁掉就是在告诉你——必须在乘法层面构造答案。乘法层面唯一自然的分解就是把除自己之外所有元素的乘积看作左边所有元素的乘积 × 右边所有元素的乘积。这个分解一旦想通前缀积和后缀积就是水到渠成的事。我在模拟面试时常跟 A 同学讲看到禁止除法先别急着想怎么绕过而是停下来想一想题目是不是在暗示一种分而治之的结构。再说 O(n) 这个约束。O(n²) 的双重循环能算出正确答案但数据量一大就不可行。这里其实藏着一个所有性能优化问题都通用的动机重复计算。每个位置的答案都要重新乘一遍所有其他元素而这些乘积之间高度重叠。优化思路就是四个字——算一次、存下来、反复用把每次重新计算变成查表复用。2. 先走两条弯路双重循环和除法方案各自翻车在哪里2.1 暴力双重循环逻辑正确但复杂度一眼超时先写最自然的暴力解法def product_except_self_naive(nums): n len(nums) res [] for i in range(n): prod 1 for j in range(n): if i ! j: prod * nums[j] res.append(prod) return res这段代码没有任何逻辑漏洞拿 [1,2,3,4] 测试照样返回 [24, 12, 8, 6]。问题出在复杂度外层 n 次内层 n 次总体 O(n²)。n 10^4 时大约要执行 10^8 次乘法肉眼可见地卡顿n 10^5 时直接不可接受。嘴上说慢没有体感我建议你在本地跑一下对比实验随机生成十万长度的数组先用暴力法跑测时间再用后面的前缀/后缀版本跑对比会非常直观。面试里不会真的让你跑数据但性能意识是基本功至少你要能一口气说清楚两个循环嵌套、每层都是 n 规模、所以是平方级这个分析过程。2.2 除法方案代码最短零元素一来就崩除法方案长这样def product_except_self_division(nums): total 1 for x in nums: total * x return [total // x for x in nums]如果输入全是正数、没有零这段代码是完美的一次遍历求总乘积再一次遍历逐个除以自身。但现实数据不会那么乖巧只要出现一个 0程序直接崩。就算你用 try/except 兜住异常返回的结果也完全没意义。再退一步手动处理零元素就要分成三种情况讨论零的个数为 0用 total // nums[i]一切正常。零的个数为 1只有零所在位置的答案是所有非零元素的乘积其余位置全为 0。零的个数 ≥ 2所有位置答案全为 0。代码至少多出三个分支每多一个分支就多一个出错可能。到这里你应该能感觉到这道题禁用除法不是在为难你而是在帮你避开一个更深的坑——把注意力引导到真正通用的前缀/后缀范式上。2.3 四种方案的横向对比方案时间复杂度空间复杂度能否处理零是否符合题目要求暴力双重循环O(n²)O(1)能不符合超时总乘积除法O(n)O(1)不能不符合禁除法前缀后缀辅助数组O(n)O(n)能符合前缀后缀原地压缩O(n)O(1)能符合满足进阶这个表格在面试时可以直接画给面试官看短短几行就能证明你不仅会写代码还清楚自己的解法在复杂度层面处于什么位置。3. 前缀积与后缀积把答案拆成左乘右两次扫描解决3.1 关键洞察排除自身恰好意味着左右两侧互不相干回到定义answer[i] 是左边所有元素乘积 × 右边所有元素乘积。因为除了 nums[i] 自己所有元素恰好分成左侧一组和右侧一组两组之间没有重叠。形式化地写left[i] nums[0] × ... × nums[i-1]左边累计乘积right[i] nums[i1] × ... × nums[n-1]右边累计乘积answer[i] left[i] × right[i]这里要特别注意边界约定left[0] 1因为第一个元素左边没有元素空集的乘积约定为 1right[n-1] 1同理。这个空集乘积为 1的约定是整个推导的地基也是很多人第一次写时容易忽略的地方。它不是随便定的而是为了保证递推式在边界位置依然成立。3.2 从左到右构造前缀积的递推以及一个常见下标错误前缀积的递推关系非常自然要得到 left[i]只需要知道 left[i-1]再乘上 nums[i-1]因为到 i-1 为止的累计乘积再乘上第 i-1 个元素恰好就是到 i 为止的累计乘积。n len(nums) left [1] * n for i in range(1, n): left[i] left[i-1] * nums[i-1]拿 [1,2,3,4] 走一遍left 初始为 [1,1,1,1]i1 时 left[1] 1×1 1i2 时 left[2] 1×2 2i3 时 left[3] 2×3 6最终 left [1,1,2,6]。这里有一个非常高发的下标错误新手容易把公式写成 left[i] left[i-1] * nums[i]这样语义就变成了截止到 i 的累计乘积包含了 nums[i] 自己与需求完全相反。记住一条判断标准left[i] 存的是当前格子左侧的信息不应该包含当前格子的元素。写完代码后可以用 left[1] 是否等于 nums[0] 来快速自检如果不等一定错了。3.3 从右到左构造后缀积逐位合并得到答案后缀积完全对称right[n-1] 1递推方向从数组尾部往头部走。right[i] right[i1] × nums[i1]意思是到 i 右侧的累计乘积等于i1 右侧的累计乘积再乘上 nums[i1]。right [1] * n for i in range(n-2, -1, -1): right[i] right[i1] * nums[i1]同样用 [1,2,3,4] 走一遍right 初始 [1,1,1,1]i2 时 right[2] 1×4 4i1 时 right[1] 4×3 12i0 时 right[0] 12×2 24最终 right [24,12,4,1]。最后一步合并对应位相乘answer [left[i] * right[i] for i in range(n)]left 是 [1,1,2,6]right 是 [24,12,4,1]逐位相乘得到 [24,12,8,6]与预期完全一致。到这一步标准的 O(n) 时间、O(n) 空间解法就完整了。3.4 为什么必须扫两遍而不能一遍走完可能是整篇文章最值得想清楚的问题能不能只从左到右扫一遍把答案全部算出来答案是不能。因为当扫描到位置 i 时你手上只有左侧累计的信息右侧的信息还完全未知必须等扫描走到数组末尾之后才有办法回头处理右侧。所以前缀/后缀类解法的模板永远是正着扫一遍收集左侧信息反着扫一遍收集右侧信息最后合并。这个两次扫描的骨架比这道题本身值钱多了。你会在后面的接雨水、前缀和等一系列题目里反复见到它它们共享同一个抽象一个位置的最终答案同时依赖左右两侧的某种累计状态。4. 空间压缩把辅助数组省到只剩一个滚动变量4.1 第一轮把答案数组当前缀积仓库题目进阶要求 O(1) 额外空间。前面的解法用了 left 和 right 两个长度为 n 的数组这显然不是 O(1)。优化的切入点是返回的 answer 数组最终反正是要给出空间的它本身就是长度为 n 的存储区为什么不在运算过程中先拿它来装前缀积这样 left 数组就可以直接省掉。第一轮扫描把前缀积写进 answeranswer [1] * n for i in range(1, n): answer[i] answer[i-1] * nums[i-1]第一轮结束后answer 里面存的就是原来 left 数组的内容相当于借用了这块存储区。此时 answer 的值是 [1,1,2,6]跟上一节 left 一致。4.2 第二轮用 right 变量边乘边写完成后缀合并后缀积没有再借数组而是改用一个滚动变量 right 边扫边更新。right 的语义是在从右往左的扫描过程中已经扫过的元素也就是当前元素右边的所有元素的累计乘积。初始 right 1因为最右边元素的右边没有元素。每走到位置 i执行两件事先 answer[i] * right把右侧累计信息乘进已有的前缀积再把 nums[i] 乘进 right为处理更左边的位置做准备。right 1 for i in range(n-1, -1, -1): answer[i] * right right * nums[i]完整代码如下def product_except_self(nums): n len(nums) answer [1] * n # 第一轮存前缀积 for i in range(1, n): answer[i] answer[i-1] * nums[i-1] # 第二轮乘后缀积 right 1 for i in range(n-1, -1, -1): answer[i] * right right * nums[i] return answer对照 [1,2,3,4] 再验证一遍第一轮后 answer [1,1,2,6]。第二轮i3answer[3] 6×1 6right 1×4 4i2answer[2] 2×4 8right 4×3 12i1answer[1] 1×12 12right 12×2 24i0answer[0] 1×24 24right 24×1 24最终结果 [24,12,8,6]正确。注意最后一次更新 right 虽然已经没有更左边的位置需要它了但这样写能让循环逻辑保持统一不影响正确性。4.3 顺序、边界、初始值三个最容易写错的细节这部分是我带人写这道题时反复踩坑的总结每条都很小但每条都能让程序跑出完全错误的结果。第一更新顺序必须是先乘 answer再更新 right。如果顺序反过来等于把 nums[i] 也乘进了当前格子的答案把除自身之外错误地变成包含自身。一个简单记忆方法answer[i] 需要的是右边的乘积nums[i] 属于左边范围不能混进 right。第二循环边界。第一轮从 i1 到 n-1第二轮从 in-1 递减到 0两个范围都必须完整覆盖。漏掉最后一个位置通常会导致边界元素答案错误而且这种错误在短数组上非常隐蔽。第三初始值。answer 数组和 right 变量的初始值都是 1乘法单位元。如果你顺手写成 [0] * n所有乘积都会被清零right 写成 0第二轮全部变 0。这类错误在键盘上很容易发生尤其是在你刚写完别的数组题之后。提示写好之后先用 [1,2,3,4] 手动推一遍再用 [1,0,3,4] 和 [1,0,0,4] 各测一次。这三个用例能覆盖绝大多数乘积类边界。5. 边界情况与实测翻车记录零、短数组、溢出5.1 含零输入的结果形态一个零和多个零完全不同前缀/后缀方案本身不怕 0不会有除零问题但如果你不理解含零输入的结果形态写自测用例时容易懵。结论分三种。没有零时结果是一般形态可能有正有负。恰好一个零时只有零所在位置的答案是所有非零元素的乘积其余位置全是 0。两个或更多零时答案数组全体为 0。这个结论的背后是同一个道理排除一个位置后剩下的元素里只要还有一个 0乘积就是 0。我第一次刷这道题时就是用含一个 0和含两个 0两种输入来自测跑通之后对算法的信心瞬间就建立起来了。你也可以用这个结论反过来检查如果输出里出现了不该出现的非零值说明滚动的 right 变量把自身乘进去了。5.2 单元素与空数组的防御性处理题目通常约定 n ≥ 2但如果你把这段逻辑封装成通用工具函数就要考虑 n 1 的场景。对于数组 [x]除了自身之外没有别的元素答案按约定是 [1]。用前缀/后缀逻辑推导也成立第一轮保持 [1] 不变第二轮 right 一直为 1answer[0] 1没有问题。空数组直接返回空数组即可。这些边界写在函数开头当防御性判断成本极低但收益不小。实际项目里工具函数被别处调用时没有人会替你想好数组会不会只有一个元素这种问题自己处理好才是负责任的写法。5.3 大数溢出不同语言的差异很大甚至需要换思路这道题的乘积可能非常大。比如 nums [100000] × 6总乘积是 10^3032 位 int 直接爆掉。LeetCode 的测试用例通常保证结果在合理范围内但真实业务不保证。Python 的整数没有上限天然安全C、Java、Go 里就要考虑用 long 或 long long再大就得用大数库。我自己在业务代码里处理过类似的除自身外乘积需求当时数据是十几个 10^4 量级的特征值乘积轻松超过 64 位。最后的解法不是硬扛大数而是转换思路把乘积转化为对数下的求和再用指数还原牺牲一点精度换取速度和空间。负数场景也要留意整体符号取决于负数的奇偶个数最好单独统计而不是靠中间值临时判断。6. 这个套路不止一道题前缀/后缀思想还能怎么用6.1 接雨水同一种骨架只是累积信息从乘积变成了最大值前缀/后缀思想最常见的延伸题是接雨水。每个柱子能接多少水等于左右两侧最高柱子的较小值减去当前柱子高度。做法从左往右扫一遍记录前缀最大值再从右往左扫一遍记录后缀最大值然后逐位置取较小值再减。这跟在数组乘积里的结构完全一致正扫、反扫、合并。差别只在于累积的信息从乘积变成了最大值。如果你把这道题练透了接雨水基本就是复制粘贴级别的改动。6.2 前缀和更常见的是加法版亲戚前缀和可能是前缀思想最广泛的应用。定义 prefix[i] 为前 i 个元素之和那么任意区间 [l, r) 的和等于 prefix[r] - prefix[l]O(1) 查询。股票买卖的最佳时机用前缀最小值二维矩阵的子矩阵和用二维前缀和。它的本质和前缀积一模一样把到当前位置为止的累计信息预存下来后续需要区间信息时直接查表。把前缀积、前缀和、前缀最大/最小值放在一起看你会抽象出一个特别有用的框架如果题目要求每个位置都依赖左边某个变换的结果和右边某个变换的结果十有八九可以用前缀/后缀两次扫描解决。拿到题先问自己两个问题左侧要累积什么状态右侧要累积什么状态定义清楚了代码结构自然就出来了。6.3 真实项目中的两个应用片段这个范式绝不是面试专属。我在做用户行为序列的特征工程时想构造某用户在时间点 t 之前的行为序列乘积收益和之后的行为序列乘积收益用来衡量当前行为在整体序列中的相对位置——这不就是这道题的前缀积加后缀积吗还有一次是在推荐系统的上下文特征里需要计算某个候选商品前面所有商品的加权累计和与后面所有商品的加权累计和同样两轮扫描搞定。所以刷题刷出来的抽象能力是真的可以迁移到生产代码里的。这也是我为什么坚持认为像除了自身之外的数组乘积这种题值得花时间把每一步推导都吃透。最后分享一个我自己多年的习惯遇到需要优化复杂度的题目先写最朴素的正确版本再写带辅助数组的版本最后再压缩空间。三步走看似费时间实际上每一版都可以独立验证正确性一旦压缩空间的版本出了 bug回头对比中间版本立刻能定位是逻辑问题还是边界问题。这道题我前前后后写过不下十遍踩过的坑基本集中在初始化、边界、更新顺序这三件事上。如果你也在准备面试建议把这几个点提前背熟并且养成提交前用三个用例自测的习惯纯正数、含一个零、含多个零。这三个用例一过这道题基本就稳了。至于正扫 反扫 合并这个句式我建议你不仅背下来还要能说清楚为什么必须扫两次——能讲明白这一句面试官对你的评价通常不会差。