LeetCode 238这道题中文名是“除自身以外数组的乘积”在字节、微软、亚马逊的算法面试题单里出现频率非常高。题目本身一句话就能讲完给你一个整数数组 nums返回一个新数组 answer其中 answer[i] 等于 nums 中除 nums[i] 之外其余元素的乘积。难的不是理解题目而是两个硬性约束不能用除法并且要求做到 O(n) 时间、O(1) 额外空间输出数组不计入额外空间。很多第一次刷到这道题的人第一反应是“先求总乘积再除以当前数”然后立刻被“不能用除法”这条规则拦下第二反应是开三个数组存左边乘积和右边乘积结果又被“O(1) 空间”卡住。所以这道题真正考察的不是你能不能算乘法而是你懂不懂“前缀积 后缀积”这种用空间换时间、再压缩空间的经典套路。这篇我就围绕这道题的两种典型解法展开重点讲清楚最优解的推导过程、实现细节以及面试现场怎么把这个思路讲得有层次感。我会先用暴力解说明为什么不行再从两个辅助数组的写法逐步压缩到一个变量最后给出完整代码、逐步推演和一套可以直接拿去自测的测试用例。无论你是刚开始刷 LeetCode 的新手还是准备面试想快速过一遍高频题的人这篇都能帮你在理解的基础上把解法真正吃透。1. 题目到底在考什么1.1 题面解读与两个硬性约束先看原题给定一个长度为 n 的整数数组 nums返回数组 answer其中 answer[i] 等于 nums 中除了 nums[i] 以外所有元素的乘积。题目下方有两个非常显眼的要求第一不能使用除法第二尝试设计 O(n) 时间复杂度和 O(1) 额外空间复杂度的解决方案。“不能使用除法”这一点很多不熟悉的同学会觉得莫名其妙我明明可以先算出整个数组的乘积 total然后 answer[i] total / nums[i]一步就出来你为什么非要拦着我这里其实藏着一个数学上的坑如果数组里有一个 0除法就会直接崩掉。比如 nums [1, 2, 0, 4]total 0那么 answer[2] 应该是 1 × 2 × 4 8但 total / nums[2] 0 / 0根本没有意义。就算用分支去单独处理 0代码也要写一堆判断完全没有数学上的优雅性。所以出题人把“不许用除法”写进题面本质上是在逼你换一种思路把“除以当前数”转成“左右两边各自乘积再相乘”。“O(1) 额外空间”则是第二个层次的考察点。注意题面说的是“额外空间”也就是说输出数组 answer 本身所占的空间不算在额外空间里。如果把这个约定理解清楚你就能明白用两个辅助数组分别存前缀积和后缀积空间是 O(n)虽然能过但不是最优解。最优解要求你只用一个滚动变量在遍历的过程中边维护右边乘积边往 answer 里填结果。1.2 暴力解与总乘积解法的两个反面教材我第一次刷这道题的时候自然而然写了双重循环对于每个 i遍历所有 j ≠ i把 nums[j] 累乘进去。这个解法的正确性没有任何问题但时间复杂度是 O(n²)。当 n 10⁵ 时要执行 10¹⁰ 次乘法直接超时。这个暴力解唯一的价值是验证小数据量下的答案对不对比如手算 [1, 2, 3, 4] 能得到 [24, 12, 8, 6]可以用来和后续的优化版本做对照。另一个很容易踩进去的坑是用“总乘积除以自身”的思路。前面说了除法方案会在 0 面前翻车。那有的同学会想我能不能算总乘积的时候跳过 0然后遍历时再根据 0 的个数分支处理可以比如先统计非零元素乘积 product再数有几个 0如果有 0 个 0每个位置都填 product / nums[i]如果正好有 1 个 0那么只有 0 所在位置填 product其余位置填 0如果有 2 个或更多 0整组答案全是 0。这个解在时间上是 O(n)空间是 O(1)看起来也不差但它依然用了除法不符合题目要求而且面试官还可能追问“如果数组里有三个 0 呢”你虽然能答上来但已经偏离了最优解的轨道。真正考察的其实是一种“区间拆分”思维对于任意位置 i答案由两部分组成左边区间 [0, i-1] 的乘积乘以右边区间 [i1, n-1] 的乘积。你不需要一次性算出整个数组的总乘积只需要分别维护“左边已经扫过的乘积”和“右边已经扫过的乘积”。2. 核心思路前缀积与后缀积的区间思维2.1 从“每个位置需要两侧信息”开始想象你站在一排人中间想计算除自己以外所有人的年龄总和最直接的办法是分别问左边所有人年龄加起来多少、右边所有人年龄加起来多少然后把两个数相加。区间乘积也是一样的逻辑answer[i] leftProduct[i] × rightProduct[i]其中 leftProduct[i] 表示 nums[0] × nums[1] × … × nums[i-1]rightProduct[i] 表示 nums[i1] × … × nums[n-1]。这种把问题拆成“左边一段”和“右边一段”各管各的、最后再合并的思路在算法里非常常见前面说的“前缀积”就是从左往右累积的乘积序列“后缀积”就是从右往左累积的乘积序列。用一句话概括你不需要知道全局所有数的乘积你只需要知道每个位置左侧的累积结果和右侧的累积结果。那为什么前缀积和后缀积能做到 O(n)关键在“累积”两个字。要计算 leftProduct[3]不需要把 nums[0]、nums[1]、nums[2] 重新乘一遍直接用 leftProduct[2] × nums[2] 就行。这是一个递推关系leftProduct[i] leftProduct[i-1] × nums[i-1]每个位置只做一次乘法所以从左往右扫一遍就能把整个 leftProduct 数组填满时间复杂度是 O(n)。2.2 先不用 O(1) 空间两个辅助数组怎么解在直接用最优解之前先看一个“更容易想到”的版本这样能更清楚后续压缩空间到底压掉了什么。第一遍从左到右维护 left 数组left[i] 存的是 [0, i-1] 的乘积初始化 left[0] 1然后递推 left[i] left[i-1] × nums[i-1]。第二遍从右到左维护 right 数组right[i] 存的是 [i1, n-1] 的乘积初始化 right[n-1] 1递推 right[i] right[i1] × nums[i1]。第三遍直接遍历answer[i] left[i] × right[i]。这个写法思路清晰时间 O(n)空间 O(n)因为额外开了两个数组。在面试中如果你先把这个版本说清楚再说“我们可以优化掉一个数组”面试官会认为你有一个梯度递进的思考过程这比上来直接甩最优解更能体现你分析问题的能力。这个两个辅助数组的版本还有一个好处它把“前缀积”和“后缀积”这两个概念单独拎出来了后续你理解滚动变量的版本时只要意识到 left 数组和 answer 数组可以合并、right 数组可以退化成一个变量就能很自然过渡到最优解。2.3 为什么能省掉一个数组回顾两个辅助数组的做法空间花在了 left 和 right 两个数组上。但实际上answer 本身就是长度为 n 的输出数组在“额外空间不计入”的约定下它完全可以先当作 left 数组用把所有左侧乘积写进去接下来只要再从右往左扫一遍用一个变量 right 维护右侧乘积边扫边把 right 乘进 answer[i] 里就能得到最终答案。这样额外的空间只有一个变量 right空间复杂度从 O(n) 降到了 O(1)。很多第一次接触这个优化的人会困惑answer 数组明明已经存在了为什么还说空间是 O(1)这里要再次强调题面的定义输出数组本身不算额外空间。如果面试官追问“如果把输出数组也算进去呢”你要能马上回答那总空间是 O(n)但额外的辅助空间确实是 O(1)。能主动把这个约定讲清楚是加分项。还有一个更直觉的类比answer 就像一张草稿纸你先把左边的乘积写在纸上然后拿着右边累积的乘积从后往前“盖”上去盖完之后纸上的内容就是最终答案。草稿纸本来就是题目要求的输出不算你额外带的工具。3. 最优解实现一次正扫加一次逆扫3.1 完整代码C 和 Python 两个版本最优解的实现只有两个循环。第一个循环从左往右用 answer 数组此时作为 left 数组记录每个位置左侧所有元素的乘积第二个循环从右往左用变量 right 记录当前位置右侧所有元素的乘积然后直接乘到 answer[i] 上。代码看着很短但几个下标的边界很容易踩坑。class Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint res(n, 1); // 第一遍res[i] nums[0] * ... * nums[i-1] for (int i 1; i n; i) { res[i] res[i - 1] * nums[i - 1]; } // 第二遍right 表示 nums[i1] * ... * nums[n-1] int right 1; for (int i n - 1; i 0; i--) { res[i] * right; right * nums[i]; } return res; } };Python 版本class Solution: def productExceptSelf(self, nums: List[int]) - List[int]: n len(nums) res [1] * n # 左侧乘积直接存到 res for i in range(1, n): res[i] res[i - 1] * nums[i - 1] # 右侧乘积用 right 滚动维护 right 1 for i in range(n - 1, -1, -1): res[i] * right right * nums[i] return res这两个版本逻辑完全一致核心就是“先从左到右填左侧积再从右到左乘右侧积”。我知道很多刷题的朋友喜欢背模板但这里我建议你至少手动推导一遍下面的例子把每一步的数组变化看明白才能真正理解这个解法的本质。3.2 逐步推演[1, 2, 3, 4] 的完整过程拿 nums [1, 2, 3, 4] 来走一遍。第一遍结束后res 数组会变成下标 i0123nums[i]1234res[i]第一遍后1126这里 res[0] 初始化为 1表示空集合的乘积res[1] res[0] × nums[0] 1 × 1 1res[2] res[1] × nums[1] 1 × 2 2res[3] res[2] × nums[2] 2 × 3 6。所以第一遍之后res[i] 存的就是下标 i 左边所有数的乘积。第二遍从右往左right 初始为 1。每一步先乘再更新 right当前 ires[i]乘之前right当前右侧积更新后的 res[i]更新 right36161 × 4 422484 × 3 1211121212 × 2 2401242424 × 1 24最终 res [24, 12, 8, 6]和暴力法算出来的完全一致。注意一个细节第二遍的更新顺序必须是“先乘 right再更新 right”顺序不能反。如果先更新 right 再乘i 3 那一步就会把 nums[3] 自己乘进去结果完全错误。这也是我后面要展开讲的“逆扫顺序”易错点。3.3 复杂度分析为什么是 O(n) O(1)时间复杂度方面第一遍循环执行了 n - 1 次乘法第二遍循环执行了 n 次乘法再加 n 次赋值总共大约 2n 次操作常数系数不影响量级所以是 O(n)。这也是题目的硬性要求因为每个元素至少要被读一次每个 answer[i] 至少要计算一次从信息论的角度讲O(n) 已经无法被优化到更低。空间复杂度方面除了返回所用的 res 数组额外只开了一个 int 变量 right。在 LeetCode 约定“输出数组不算额外空间”的前提下额外空间是 O(1)。当然如果你严格地把 res 数组也计入总空间那总空间是 O(n)但“额外辅助空间”确实是 O(1)。面试里碰到“这个解法空间复杂度到底是多少”的追问时一定要把这两个口径区分清楚不要含糊。这看似是小事但能体现你对空间复杂度定义的理解够不够严谨。4. 关键细节、边界测试与面试避坑4.1 数组里有 0 怎么办这是这道题问得最多的问题之一。我们的最优解完全不需要为 0 做任何特殊处理因为每个位置的结果都是“左侧乘积 × 右侧乘积”而乘法天然对 0 免疫只要左侧或右侧任意一侧包含 0那么乘积自然是 0如果当前元素是 0那么答案里的 0 只可能来自“下标和 0 的位置不重合”的某种组合。换句话说0 的干扰已经被分解到了两侧区间里不需要额外判断。我们拿几个典型例子验证一下。第一个例子 nums [0, 1, 2, 3]。期望答案是 [1×2×3, 0×2×3, 0×1×3, 0×1×2] [6, 0, 0, 0]。用代码跑一遍第一遍 res 变成 [1, 0, 0, 0]第二遍从右往左i 3 时 res[3] 0 × 1 0i 2 时 right 3res[2] 0 × 3 0i 1 时 right 6res[1] 0 × 6 0i 0 时 right 6res[0] 1 × 6 6。结果完全正确。第二个例子 nums [1, 2, 3, 0]。期望答案是 [2×3×0, 1×3×0, 1×2×0, 1×2×3] [0, 0, 0, 6]。跑一遍第一遍 res [1, 1, 2, 6]第二遍 i 3right 1res[3] 6 × 1 6right 更新为 0i 2res[2] 2 × 0 0i 1res[1] 1 × 0 0i 0res[0] 1 × 0 0。结果同样正确。这两个例子很重要因为它们正好覆盖了“只有一个 0 在开头”和“只有一个 0 在结尾”两种边界。如果你之前总是担心“有 0 是不是要特判”看完这两个例子的手推过程就能彻底把心放回肚子里了。4.2 为什么题目强调“不要用除法”除了 0 的问题还有一个数学层面的原因除法会引入精度和整除问题。在整数数组里如果 total 不能整除 nums[i]直接除会得到截断后的错误结果比如 total 7nums[i] 3得出 2 而不是 2.333。虽然本题数据保证答案一定是整数但用除法仍然要额外处理 0 的情况代码会变得丑陋且容易漏边界。从面试角度讲你必须主动点出“我不用除法是因为可能存在 0而且题目本身也做了这样的限制”。这句话不仅是为了正确性也是为了表明你不是只会背模板而是真的考虑过为什么要这么设计。如果你在面试时能补充一句“如果题目允许用除法且明确数组没有 0那我也可以先算总乘积再逐个除但那样就失去了这道题的考察意义”会比单纯报答案更能让面试官印象深刻。记忆技巧是遇到这种“每个位置的结果依赖整体所有元素之间的关系”的题先想一想要不要用“前缀×后缀”的框架。只要你能说出“左侧乘积和右侧乘积相乘”这个核心思想哪怕代码写慢一点思路方向也对了。4.3 测试用例 SOP 与常见误区速查表我刷题有一个习惯写完代码之后不是直接提交而是先用几个“边界小样本”在脑子里过一遍。这里有一套适合这道题的测试 SOP。第一类普通正数数组比如 [1, 2, 3, 4]期望 [24, 12, 8, 6]用来验证基本流程。第二类包含 0 的数组比如 [0, 1, 2, 3]、[1, 2, 3, 0]期望分别是 [6, 0, 0, 0] 和 [0, 0, 0, 6]用来验证“不用除法也能正确应对 0”。第三类全 1 数组 [1, 1, 1, 1]期望 [1, 1, 1, 1]用来验证乘法累积不会出错。第四类是负数数组 [-1, -2, 0]期望是 [0, 0, 2]验证负数和 0 同时存在时符号没有问题。第五类是长度为 2 的最小数组 [5, 7]期望 [7, 5]验证最简边界。常见误区方面我整理了一张速查表方便你在复习时快速排查常见问题原因分析正确做法第一遍循环从 i 0 开始误以为 res[0] 也要计算res[0] 表示“左侧没有元素”应初始化为 1循环从 i 1 开始第二遍循环先更新 right 再乘会把当前元素 nums[i] 自己乘进去必须先 res[i] * right再 right * nums[i]第二遍循环用 size_t 类型的 i当 i 0 后继续执行 i-- 会变成最大值死循环用 int 类型判断条件写 i 0额外开 left、right 两个数组空间 O(n)不是最优解让 res 先存左积用一个变量滚动维护右积忘记将 res 初始化为 1第一遍里 res[i-1] 是 0导致整个结果全是 0初始化 vector res(n, 1)用除法计算答案数组含 0 时除数为 0且不符合题目要求采用前缀积 × 后缀积完全避开除法其中“第二遍循环用 int 类型”这一点看起来特别基础但我真在面试模拟里见过不少同学栽在这里。C 里如果写成 for (int i n - 1; i 0; i--) 没问题但写成 for (int i n - 1; i 0; --i) 也没问题一旦把 i 的类型误写成 size_ti-- 从 0 变到无符号最大值循环条件 i 0 恒成立就会死循环。这个点单独拿出来记忆能帮你省掉一次线上提交超时的尴尬。4.4 面试现场怎么把最优解讲清楚很多同学解题能力强但面试表达拉胯原因在于一上来就甩最优解。如果面试官没有看过这道题你直接给出 O(1) 空间解对方可能会一脸问号你的 right 变量是干嘛的res 填了两遍第二遍覆盖了第一遍的东西怎么结果反而对我的建议是分三步走。第一步说清楚暴力解是双重循环复杂度 O(n²)不满足要求。第二步引入“左侧乘积 × 右侧乘积”的框架先给两个辅助数组的版本说明时间和空间分别是 O(n) 和 O(n)这个版本是对的但还有优化空间。第三步把 left 数组合并进 res把 right 数组压缩成一个变量强调“输出数组不计入额外空间”最终达到 O(n) 时间 O(1) 空间。这种层层递进的讲述方式不仅让面试官跟得上也展示了你从“能解”到“解好”的完整思考路径。另外面试中写代码之前最好用一句话点破核心当前位置的答案等于左侧所有数乘积乘上右侧所有数乘积。这句话是整道题的题眼先说出来代码写起来就顺理成章了。5. 举一反三这类题还能怎么变5.1 前缀积的通用套路LeetCode 238 只是“前缀积”套路的一个代表。类似地“前缀和”也是算法面试的高频考点比如 LeetCode 303 区域和检索就是一个典型的前缀和题LeetCode 560 和为 K 的子数组则把前缀和和哈希表结合在了一起。这两种“前缀结构”的核心思想一脉相承把一段区间内的连续计算结果通过预处理存到一个累计序列里查询时用两个累计值相减或相乘得到区间结果避免每次重新遍历。对于“前缀积”这个套路你可以记住一个更通用的形态当问题要求计算“每个位置与两侧区间有关的结果”时先想想能不能把结果拆成 left[i] 和 right[i] 的某种运算如果能拆再用一个数组存左边、一个变量滚动算右边。LeetCode 238 是乘法如果把乘号换成加号很多题也可以直接套同构的思路换成最大值、最小值只要满足“可组合”的性质也能做类似处理。5.2 和“接雨水”这类两侧信息题的对比LeetCode 42 接雨水也是一道经典的两侧信息题每个位置能接多少水取决于它左右两侧最大高度的较小值减去当前高度。它的常用解法之一也是“从左到右求 leftMax从右到左求 rightMax”再逐位计算。这道题和 LeetCode 238 在思维模型上非常相似区别只在于一个是“两侧乘积”一个是“两侧最大值”。如果你能把这两道题放在一起刷会发现它们用的是同一套“两头扫描”的骨架。对比来看LeetCode 238 的左右两边是独立的乘起来就行LeetCode 42 的左右两边则要取较小值因为低于两侧最高高度才能积水。你可以在笔记里给这类题做一个“两侧扫描”专栏记录每道题的拆法、状态定义、左右扫描的方向以及最后合并的运算符。这样刷三到五道题之后你就能很自然地形成条件反射看到“每个位置的结果只依赖它左右两边的信息”这类描述第一反应就是“先左边扫一遍再右边扫一遍”。5.3 刷题建议与心态调整最后聊点刷题以外的体会。LeetCode 238 这道题我见过有人背了十遍还是记不住原因就是没有理解“前缀积”这个中间状态的意义。我自己的刷题方法是每道核心题都手动推导一个完整小例子把每一步数组的变化写出来就像上面 [1, 2, 3, 4] 的表格一样。一旦你能在白纸上不靠记忆地把这个过程推出来代码自然就写出来了而且遇到变体也不会慌。如果你现在正卡在“别人都说简单但我总是记不住”的阶段我的建议是先放下代码只在纸上画数组。画一个长度为 4 的格子第一遍从左往右把“左侧乘积”填进格子里第二遍用一个箭头标记“右侧乘积”一格一格往左移。把这个过程在纸上做三遍很多抽象的地方会突然变得很具体。这比盯着题解看十遍有用得多。我用一种很口语化的方式总结这道题的核心左边算一遍右边算一遍两边乘起来答案就在眼前。记住这一句话你把这道题讲给别人听的时候思路一定是清晰的。