LeetCode Hot100 刷到第 13 题238. 除了自身以外数组的乘积。坦白说这题我刚看到的时候第一反应就是“先求全部元素的乘积再逐个除以当前元素”。这个思路在数学课上没问题一提交就被教育了题目明确写着“请不要使用除法且在 O(n) 时间复杂度内完成”。更难受的是数组中一旦出现 0整个“先乘后除”方案直接崩掉你还要单独去数 0 的个数、判断 0 出现在哪个位置代码越写越丑。这道题适合已经刷完简单题、想进阶到中等难度的人也适合正在按 Hot100 题单系统性补算法的朋友。它表面上考的是数组遍历实际上考的是“前缀信息复用”和“空间优化”这两个高频思维和 238 同类的题目在面试里出现率极高。这篇就把这题从暴力思路一路讲到常量额外空间的优雅解法顺便把过程中容易踩的坑一次性说清楚。1. 先搞清楚这题到底在问什么1.1 题目解读与易错点题目给一个整数数组nums返回一个新数组answer其中answer[i]等于nums中除了nums[i]以外所有元素的乘积。举个例子输入nums [1,2,3,4]输出必须是[24,12,8,6]。手工验证一下answer[0] 2 * 3 * 4 24answer[1] 1 * 3 * 4 12answer[2] 1 * 2 * 4 8answer[3] 1 * 2 * 3 6这个例子看上去人畜无害很多新手就掉进“总乘积除以当前值”的陷阱。我先说结论如果题目没有禁止除法这个思路在全是正数、没有 0 的情况下是对的但工程上并不可取。原因有两个一是题目故意说“不要用除法”面试官想看你能不能绕过除法二是数组中一旦出现 0总乘积会变成 0除以当前值要么结果是 NaN要么是 0全都不对。还有一个隐形易错点题目要求“所有元素乘积不会溢出 32 位整数”这是 LeetCode 给的一个宽松条件意味着你不需要在代码里额外处理大数溢出。但做题时还是建议用 64 位中间变量去累积避免某些变体测试用例在本地跑的时候出现诡异结果。1.2 为什么第一反应“全部乘起来再除以自身”是个坑我先把这个坑详细拆开。假设nums [1,2,0,4]总乘积是1 * 2 * 0 * 4 0。如果你用0 / nums[i]在大部分语言里会得到0但正确答案是什么answer[0] 2 * 0 * 4 0answer[1] 1 * 0 * 4 0answer[2] 1 * 2 * 4 8answer[3] 1 * 2 * 0 0只有当当前元素是那个唯一的 0 时答案才是非零的。也就是说你用除法根本没法区分“某个位置是 0”和“乘积是 0”这两种情况只能额外统计数组中 0 的个数再分支处理。更麻烦的是语言层面的除法陷阱。整数除法在遇到0 / 0时直接抛异常很多刷题环境里这种运行时错误非常难查。即便你提前做了if (nums[i] ! 0)的判断代码也已经膨胀到和题目初衷背道而驰了。所以我把话说直白一点这道题的正确姿势就是在加法/乘法维度上做“借位”别去碰除法。2. 从 O(n²) 到 O(n)前缀积思想拆解2.1 暴力法的复杂度天花板最容易想到的暴力法就是两层循环。外层遍历i内层遍历j把所有j ! i的元素乘起来。伪代码大概是def product_except_self(nums): n len(nums) res [0] * n for i in range(n): prod 1 for j in range(n): if j ! i: prod * nums[j] res[i] prod return res时间复杂度和空间复杂度是什么样的外层i有n次内层每次要扫描几乎全部n个元素所以是O(n^2)。LeetCode 上n最大能到10^510^5的平方就是10^10任何语言都很难在 1 秒内跑完。暴力法的问题不在于思路错而在于重复计算太多。你算answer[0]时乘了 1、2、3、4算answer[1]时又乘了 1、2、3、4中间大量乘积被反复计算。人脑算这道题的时候不会重新乘一遍而是会盯着一部分乘积复用。算法优化的本质就是把这种直觉结构化。2.2 前缀积与后缀积把乘积累积两层数组我们引入两个概念前缀积和后缀积。prefix[i]表示nums[0]到nums[i]所有元素的乘积。suffix[i]表示nums[i]到nums[n-1]所有元素的乘积。那么对于目标数组answer[i]有一个很关键的观察answer[i] nums[0] * ... * nums[i-1] * nums[i1] * ... * nums[n-1]这正好等于前缀积到i-1为止 乘以 后缀积从i1开始如果用prefix[i-1]表示nums[0..i-1]的乘积用suffix[i1]表示nums[i1..n-1]的乘积那公式就是answer[i] prefix[i-1] * suffix[i1]边界情况单独处理当i 0时prefix[i-1]不存在此时左边没有任何元素等价于乘 1所以answer[0] suffix[1]。当i n-1时suffix[i1]不存在此时右边没有任何元素等价于乘 1所以answer[n-1] prefix[n-2]。先花O(n)时间构造prefix和suffix再花O(n)时间构造answer总体时间复杂度O(n)空间复杂度O(n)。这是最容易理解也最不容易写错的版本适合面试时先讲思路。我用nums [1,2,3,4]手工推一遍prefix [1, 2, 6, 24]suffix [24, 24, 12, 4]然后answer[0] prefix[-1] 不存在所以是 1 * suffix[1] 24answer[1] prefix[0] * suffix[2] 1 * 12 12answer[2] prefix[1] * suffix[3] 2 * 4 8answer[3] prefix[2] * suffix[4] 不存在所以是 6 * 1 6结果完全正确。有了这层“前缀 后缀”的直觉后面所有优化都只是在这个框架上做空间压缩。2.3 空间压缩的第一步输出数组暂存左侧乘积先别急着追求 O(1) 额外空间我们做一步温和的优化只保留左边的前缀积数组右边的乘积用滚动变量来算。具体做法是这样的初始化一个数组answer长度为n。第一遍从左往右让answer[i]存下“nums[0]到nums[i-1]的乘积”也就是nums[i]左侧所有元素的乘积。这一步之后answer[i]已经等于最终答案的左边一半。然后从右往左遍历用一个变量right来累积“当前元素右侧所有元素的乘积”每到一个位置就把answer[i] * right这样answer[i]就变成了左侧乘积乘右侧乘积得到完整答案。这个方法空间复杂度从 O(n) 降到了 O(1)但只用了输出数组本身。LeetCode 的进阶要求是“常数空间”因为输出数组本来就要返回不算额外空间所以这种写法完全满足要求。3. 常量额外空间的完整实现3.1 两次遍历的代码模板Python / Java / C / Go我把最核心的写法整理出来这是刷题社区里公认最简洁的版本。先用 Python 演示from typing import List class Solution: def productExceptSelf(self, nums: List[int]) - List[int]: n len(nums) ans [1] * n # 第一遍从左到右ans[i] nums[0..i-1] 的乘积 for i in range(1, n): ans[i] ans[i - 1] * nums[i - 1] # 第二遍从右到左用 right 累积右侧乘积 right 1 for i in range(n - 1, -1, -1): ans[i] * right right * nums[i] return ansJava 版本class Solution { public int[] productExceptSelf(int[] nums) { int n nums.length; int[] ans new int[n]; ans[0] 1; for (int i 1; i n; i) { ans[i] ans[i - 1] * nums[i - 1]; } int right 1; for (int i n - 1; i 0; i--) { ans[i] * right; right * nums[i]; } return ans; } }C 版本class Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint ans(n, 1); for (int i 1; i n; i) { ans[i] ans[i - 1] * nums[i - 1]; } int right 1; for (int i n - 1; i 0; --i) { ans[i] * right; right * nums[i]; } return ans; } };Go 版本func productExceptSelf(nums []int) []int { n : len(nums) ans : make([]int, n) ans[0] 1 for i : 1; i n; i { ans[i] ans[i-1] * nums[i-1] } right : 1 for i : n - 1; i 0; i-- { ans[i] * right right * nums[i] } return ans }四个语言的核心逻辑完全一致。第一遍从左往右把左侧乘积装进ans第二遍从右往左用right补上右侧乘积。如果面试官问你怎么优化直接把这两遍遍历的思路讲出来远比背代码有说服力。3.2 变量更新的顺序为什么不能乱我见过不少人在第二次遍历时把顺序写反导致结果全是 1 或者整体多乘一遍。这里要特别强调一下。right变量在第二遍中代表的是“已经遍历过的右侧元素乘积”。当指针i还在n-1时它右侧没有任何元素所以right初始必须是1。然后执行两步先用当前right更新ans[i]。再把nums[i]乘进right为下一个位置做准备。如果反过来先执行right * nums[i]再更新ans[i]那么ans[n-1]就会多乘一个nums[n-1]而ans[n-1]原本应该是“除自己外所有元素乘积”多乘自己之后答案直接错了。我用一个具体例子推演nums [1, 2, 3, 4]正确写法下第二遍过程如下i更新前 rightans[i] 更新后更新后 right31ans[3] 6 * 1 61 * 4 424ans[2] 2 * 4 84 * 3 12112ans[1] 1 * 12 1212 * 2 24024ans[0] 1 * 24 2424 * 1 24第一遍之后ans [1, 1, 2, 6]分别代表nums[0]到nums[i-1]的乘积。跑完第二遍得到[24, 12, 8, 6]正确。如果你把right * nums[i]提前i 3那一轮right先变成 4再算ans[3] 6 * 4 24但正确答案是 6直接错了。这种 bug 在力扣提交里特别常见不是思路问题纯粹是更新顺序踩坑。3.3 复杂度分析与题目边界这题要求时间复杂度 O(n)我们做到了空间复杂度 O(1)不算输出数组我们也做到了。如果你用的是“前缀数组 后缀数组”那个版本空间复杂度是 O(n)虽然能 AC但面试官很可能跟一句“能不能再优化一下”所以我建议直接掌握常量空间的版本。关于边界LeetCode 原题约束1 nums.length 10^5所以数组至少有一个元素。当n 1时answer[0]是“除自身外所有元素乘积”没有其他元素约定为1。上面的代码跑nums [5]第一遍ans [1]第二遍right 1ans[0] * 1结果为1没问题。另外题目说“所有元素乘积不会溢出 32 位整数”这句话保证了中间变量乘到最大值时不会爆炸。但我自己在本地测试的时候依然会把中间变量声明成long或int64因为一旦你把这个解法搬到其他类似场景输入数组可能全是10^9量级连乘几个就会溢出。4. 实操过程中真正容易踩的坑4.1 除零陷阱与“不用除法”的深层原因网上有很多人讨论“如果允许用除法和额外处理 0能不能秒掉这题”。我直接说能但不推荐原因有二。第一代码复杂度会上升。你需要统计 0 的个数0 个 0可以直接用总乘积除以每个元素1 个 0只有 0 所在位置的答案是总乘积其他位置全是 02 个及以上 0所有答案全是 0。这个分支逻辑写到代码里很容易漏而且面试官一眼就能看出你还在依赖除法。第二除法和累乘的数值稳定性不同。Python 里整数除法要处理负数取整方向C 里整数除法遇到 0 直接 UBJavaScript 里1 / 0结果是Infinity这些在刷题环境里都是雷。与其费劲处理各种语言特性不如老老实实走前缀积路线。我整理了一个对比表格方便你直观理解方案时间复杂度空间复杂度能否处理 0是否遵守题目要求暴力双层循环O(n²)O(1)能能但超时总乘积 除法O(n)O(1)需分支处理不能题目禁用除法前缀积数组 后缀积数组O(n)O(n)能能输出数组存储左侧乘积 右侧滚动变量O(n)O(1)能能推荐4.2 单元素、空数组、前缀积溢出的边界处理先说空数组。力扣原题虽然保证n 1但很多公司面试官会追加一句“如果空数组呢”。合理行为是返回空数组[]或者抛异常取决于约定。如果你代码里直接用ans[0] 1空数组会越界所以严谨一点可以先判断if n 0: return []。再看单元素数组。上面已经验证过返回[1]是符合定义的。不过有一点要注意数学上“空乘积”定义为 1这不是 LeetCode 拍脑袋定的而是排列组合和数论里的标准约定。明白这个约定你就能解释为什么right初始值是 1 而不是 0。前缀积溢出是另一个隐藏话题。题目说不会溢出但为了保险我在第一遍和第二遍累积乘法时刻意用long类型的变量最后转回输出数组时才收窄。LeetCode 上很多“差一个用例没通过”的报错排查到最后都是局部变量溢出导致的建议一开始就养成好习惯。4.3 刷题现场的经验笔记我第一次做这题的时候直接卡在“不用除法”上花了十分钟才绕到前缀积。后来我总结出几个现场经验现在分享给你。先画图不先写代码。把nums [1,2,3,4]的左侧乘积和右侧乘积分别列两行用箭头标出来思路马上清晰。写第二遍遍历时在注释里写清楚“right 表示当前元素右侧所有元素的乘积”防止回头看代码时忘记变量含义。提交前手动跑两个极端用例全是 1 的数组以及包含 0 的数组。前者验证乘法正确性后者验证边界逻辑。如果面试官要求“不能使用额外数组”你直接说“输出数组不算额外空间”这个约定并把right变量作为唯一的额外存储这是面试官最想听到的回答。我自己还在本地记录了这题的耗时n 100000全随机整数Go 版本跑完不到 8 毫秒。O(n) 和 O(n²) 的差距在这种规模下一目了然。5. 一道题带出一类题前缀积的扩展思路5.1 变体构建左右前缀数组的直观版如果你在面试初期我建议还是先把“左右前缀数组”版本讲清楚再去讲优化版。两者的关系是优化版是直观版的压缩但直观版更容易推导也不容易在细节上翻车。直观版代码长这样def product_except_self_verbose(nums): n len(nums) left [1] * n right [1] * n for i in range(1, n): left[i] left[i - 1] * nums[i - 1] for i in range(n - 2, -1, -1): right[i] right[i 1] * nums[i 1] return [left[i] * right[i] for i in range(n)]这里的left[i]是nums[0..i-1]的乘积right[i]是nums[i1..n-1]的乘积最后每个位置相乘。这么写虽然多用了一个数组但每一步的语义都和公式一一对应面试时作为“解法一”讲出来非常自然。从工程角度看左右数组还有一个好处如果后续需要频繁修改nums中的某个元素你可以只更新对应的前缀和后缀数组而不需要重新 O(n) 计算。这在数据流类题目中是常见套路。5.2 变体可修改数组版本与数据流场景把 238 稍微改一改就变成另一道高频题设计一个数据结构支持更新某个元素的值并查询“除某个位置外所有元素的乘积”。常见做法是维护一个总乘积和一个 0 的计数。当数组中 0 的个数为 0 时用总乘积除以当前值当 0 的个数为 1 时只有那个 0 所在位置的答案等于总乘积其他位置全是 0当 0 的个数大于等于 2 时所有位置答案都是 0。这个思路来自于对 238 除法的讨论但在“可修改”场景下反而成了最优解。再往深走一步如果数组长度很大而且查询区间不是“除了自身”而是任意区间[l, r]的乘积那就要用线段树或者稀疏表来维护区间乘积。238 题前缀积的思想是这些高级数据结构的地基理解它之后再看区间查询会顺畅很多。我做相关题目时还发现一个规律Hot100 里很多题都在反复使用“左侧信息 右侧信息”的组合。比如 42. 接雨水就是用左边最大值和右边最大值的较小者减去当前高度比如 84. 柱状图中最大的矩形也是左右扩展的思维。238 练熟之后再做这些题会有一种“原来都是同一个套路”的豁然感。5.3 相关 Hot100 题目的联系Hot100 题单刷到 13/100 的时候你可以明显感觉到题与题之间是有联系的。238 和以下几道题都共享一些底层思维接雨水对每个位置取左侧最大值和右侧最大值的较小者再减去当前高度本质是“左右信息复用”。乘积最大子数组要同时维护最大值和最小值因为在处理负数时一个很小的负数乘负数可能变成最大。这和 238 的“连着乘”直觉有直接关系。和为 K 的子数组使用了前缀和思想前缀和是“前缀积”的加法版本。和可被 K 整除的子数组前缀和配合余数数组用的也是同一个信息累计框架。所以说238 并不是一道孤立的题。它教给你的是“如何用一次遍历把某个方向上的累积信息存下来再用第二次遍历去补上另一个方向”。这个思维在数组类题目里属于基础中的基础值得多花时间吃透。我个人刷题有个习惯中等题至少写两种解法。第一遍按最直观的数组版本过第二遍再优化空间。238 这种题特别适合这个练习方式因为从 O(n) 空间优化到 O(1) 空间只改了半个循环却能把“输出数组能不能算额外空间”“滚动变量怎么更新”这些细节全部串起来。最后再分享一个小技巧刷这题的时候别只盯着代码跑通拿笔在纸上把ans数组每一轮的值写出来写个两三组用例你就再也不会忘记为什么right要最后更新了。