LeetCode 第 238 题“除自身以外数组的乘积”是我刷题单里印象很深的一道它在 LeetCode 热门 100 题里排得上号几乎所有大厂的算法面试都喜欢拿它当试金石。题目本身一句话就能讲完给你一个整数数组 nums返回一个数组 answer其中 answer[i] 等于 nums 中除了 nums[i] 之外其余所有元素的乘积。举个小例子nums [1, 2, 3, 4] 时answer [24, 12, 8, 6]。第一次看到这道题的人大多会觉得简单然后下意识想把所有数乘起来再除以当前位置的数结果被题目里“请不要使用除法”这六个字拦住。真正做进去之后你会发现它考察的远不止乘法而是数组遍历顺序、临时状态复用和空间复杂度优化的一整套思维方式。这篇文章我打算从题目本身的限制条件讲起把前缀积乘后缀积的核心思路拆开再用手写推演的方式把最优解每一步跑通最后把数组里有零、数组长度为一、多语言实现差异这些边界问题一并聊透。无论你是刚刷 LeetCode 的新手还是准备面试想温习经典题的开发者这题都值得花半小时仔细吃透。1. 先弄清题目到底在考什么1.1 一句废话都不说地读懂题意题目要求你返回一个新数组这个数组的第 i 个位置是原数组里除掉第 i 个数本身之后其余所有数的乘积。以 [1, 2, 3, 4] 为例第一个位置要算的是 2 × 3 × 4 24第二个位置要算的是 1 × 3 × 4 12第三个位置是 1 × 2 × 4 8第四个位置是 1 × 2 × 3 6。注意这里不含当前数字本身这句话听着像废话实际上是最容易让人犯迷糊的地方。很多刚接触这道题的人会把它和“求整个数组的乘积”混在一起想。如果你先求了全数组乘积再逐位相除本质上你已经换了道题。面试官想看到的是你围绕“除自己之外”这个限定来做文章而不是绕开它。题目给出的输入数组长度最大可以达到 10^5这意味着两层循环的暴力做法不可能通过所以第一个要接受的事实是你必须在线性时间内完成。这道题在原题里还附带了两个进阶要求一是不允许用除法二是尽可能用常数空间。前者把最容易想到的解法直接堵死后者把习惯开两个辅助数组的思路也一并堵死。能同时满足这两个条件的解法才是这道题真正想让你给出的答案。1.2 为什么“禁止除法”是一条送命题第一反应用总乘积除以当前数这个思路不是不行而是被题目刻意禁止了。这里我得展开讲讲禁止的原因因为搞清楚这个你才能明白出题人真正想考你什么。首先数组里可能有 0。一旦 nums 里出现一个 0total 全数组乘积就等于 0你用 total 除以 nums[i]只有 nums[i] 不为 0 的那些位置结果是对的nums[i] 正好是 0 的那个位置会直接出现 0 除以 0 的尴尬。如果数组里有两个 0那除法的思路就更没法收场你不得不先统计零的个数再分情况讨论。也就是说除法解法不是写不出来而是被边界条件逼到写满一个 if-else 分支树。其次除法会引入符号和精度问题。C 和 Java 里整数除法直接截断数组里如果有负数你算出来的商可能因为符号方向对不上而出现偏差。当然你可以小心处理但面试官不会欣赏你在这些细节上绕路。题目真正想让你走的路是把每个位置的答案拆成两部分左边所有数的乘积乘上右边所有数的乘积。这个思路叫“前缀积 × 后缀积”不依赖除法零元素也天然能正确处理因为 0 参与乘法得到的就是 0。1.3 时间空间双重限制背后的潜台词LeetCode 原题最常见的版本是要求在 O(n) 时间内完成并且尽量用 O(1) 额外空间。注意这个 O(1) 额外空间里输出数组本身是不算进去的。这句话就是解题的关键钥匙——既然你要返回一个答案数组这个数组必然存在那你为什么不提前把它利用起来让它先暂存中间结果呢这种“先把答案数组当草稿纸之后再修正”的手法在很多数组题里都出现过。最典型的就是中心下标问题先算总和再从左往右维护左边和比较当前位置左右两边是否相等。除自身以外数组的乘积比中心下标多绕了一层因为它需要两个方向的信息而不是一个方向的累加。弄明白时间空间限制之后你会发现这题的考察层次特别清晰第一层是暴力双重循环第二层是左右乘积数组第三层是在输出数组上原地操作。每一层都有明确的代码量和思路复杂度差异所以面试官特别爱用它来判断候选人对数组遍历细节的把控程度。网上搜这道题时还会带上“指针数组”“数组去重”“数组方法”这些关联词其实都是在数组这个话题下打转想把这题彻底吃透索引、遍历、边界条件这三个基本功必须先过关。2. 核心思路拆解从两个辅助数组到一个变量2.1 用一排人的游戏建立直觉我自己讲这道题的时候喜欢用一排人来打比方。假设你面前站了一排人每个人手里拿一个数字牌现在游戏规则是每个人都要报出一个结果这个结果等于他左边所有人手里数字的乘积再乘上他右边所有人手里数字的乘积但不包括他自己。那你要做的工作就分两步。第一步从最左边的人开始往右走每个人记下“我左边所有人的乘积”第二步从最右边的人开始往左走每个人再把“我右边所有人的乘积”乘到自己记下的数字上。两步走完所有人手里的结果就是正确答案。这个比喻看起来简单但它其实完整对应了代码里的两个循环一个正向遍历算前缀积一个反向遍历算后缀积。用公式表达就是answer[i] prefix[i] * suffix[i]其中 prefix[i] 是 nums[0] 到 nums[i-1] 的乘积suffix[i] 是 nums[i1] 到 nums[n-1] 的乘积。边界上的处理也很自然第 0 个元素左边没有任何元素所以 prefix[0] 1最后一个元素右边没有任何元素所以 suffix[n-1] 1。这个 1 在数学上叫空乘积是乘法单位元它不来自数组里的任何一个数。2.2 第一版解法左右乘积数组空间 O(n)先把最直白的版本写出来。声明两个和 nums 等长的数组 L 和 RL[i] 存第 i 个位置左边所有数的乘积R[i] 存右边所有数的乘积。第一个循环从左往右填充 L第二个循环从右往左填充 R第三个循环把两个数组逐位相乘得到答案。def productExceptSelf(nums): n len(nums) L [1] * n R [1] * n ans [1] * n for i in range(1, n): L[i] L[i - 1] * nums[i - 1] for i in range(n - 2, -1, -1): R[i] R[i 1] * nums[i 1] for i in range(n): ans[i] L[i] * R[i] return ans这个版本能通过所有测试逻辑也最容易理解但它花了两个额外数组空间复杂度是 O(n)。面试官看完几乎一定会追问一句能不能把空间省下来如果你这时候思路清晰直接把 R 数组干掉用一个变量边走边累乘就能进入下一层。需要留意的是边界初始化的位置。L[0] 必须等于 1因为第 0 个元素左边没有数字空积是 1R[n-1] 同理。很多新手第一次写会顺手把 L[0] 设成 nums[0]结果第一个位置答案直接错掉。判断方法很简单你看看 L[i] 的定义它包含的是 nums[0] 到 nums[i-1]那就绝不能让 nums[i] 混进去。2.3 最优解复用输出数组额外空间 O(1)到了这一步核心技巧就是把答案数组先当成 L 来用。答案数组反正要返回空间不算额外开销那不如先让它存左边乘积再从右往左用一个滚动变量 suffix 把右边乘积补上。完整流程分成两大步。第一步ans[0] 初始化为 1然后从左往右遍历令 ans[i] ans[i-1] * nums[i-1]。这一步结束之后ans[i] 的意义就是“第 i 个位置左边所有数的乘积”和上一版 L 数组一模一样。第二步初始化 suffix 1从右往左遍历先做 ans[i] ans[i] * suffix再让 suffix suffix * nums[i]。这里的 suffix 在每轮循环开始时恰好等于 nums[i1] 到 nums[n-1] 的乘积。def productExceptSelf(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] # 右边乘积用一个滚动变量 suffix 从右往左补 suffix 1 for i in range(n - 1, -1, -1): ans[i] * suffix suffix * nums[i] return ans第二步里“先乘再更新”这个顺序是整个题最关键的细节。如果你手滑先写了 suffix * nums[i]再写 ans[i] * suffix那 ans[i] 就会把 nums[i] 自己也算进去导致结果等于“包含自己的总乘积”。从右往左扫的时候当前元素还没被计入后缀积所以才叫“右侧乘积”。同样的逻辑用 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 suffix 1; for (int i n - 1; i 0; --i) { ans[i] * suffix; suffix * nums[i]; } return ans; } };我见过很多人把这段代码背下来但被问到“为什么先乘 suffix 再更新 suffix”就卡住。如果出现这种情况说明还没有真正掌握面试时大概率会被追问到露馅。理解滚动变量背后含义的方法是亲手推一遍这也是我下一节要做的。2.4 为什么这种“先存一半再补一半”的思路值得记住除自身以外数组的乘积不是孤立的一道题它背后是一大类“需要左右两侧信息”的数组问题。遇到这类问题时第一反应应该是能用一次遍历解决的问题绝不循环嵌套能在已有数组上原地操作解决的问题绝不新建辅助数组。比如 LeetCode 42 接雨水、LeetCode 135 分发糖果它们都需要同时考虑左边和右边的约束常见解法之一就是分别遍历两次维护数组。你把除自身以外数组的乘积吃透了再去看那些题会觉得顺手很多因为两次遍历、左信息右信息这种骨架你已经搭好了。这也是我一直建议大家以题带面地刷面试题的原因单刷一道题价值有限把一道经典题理解到能迁移才算真正吃透。3. 手把手推演从暴力到最优解的全过程3.1 暴力解法为什么连示例都撑不住先把最简单也最不推荐的办法写出来作为反面参照。对每个位置 i开一个内层循环把除 i 之外的所有数乘起来。代码异常直白def productExceptSelf(nums): n len(nums) ans [] for i in range(n): p 1 for j in range(n): if j ! i: p * nums[j] ans.append(p) return ans这个版本逻辑没错但时间复杂度是 O(n^2)。当 n 10^5 时运算量能到 10^10 这个量级跑常规用例都会超时。面试场景里如果你真写了这个面试官大概率会停顿一下然后说“能不能想一想更快的办法”。这时候你可以顺势把话题引向“每个位置的答案可以拆成左边和右边两部分”不至于冷场。不过暴力版本也有一点价值它能帮你确认题意。比如 [1, 2, 3, 4] 通过暴力手算得到 [24, 12, 8, 6]如果你自己想出的最优解也得到同样结果说明你的思路至少没有在一开始就跑偏。3.2 用 [1, 2, 3, 4] 完整跑一遍最优解这一步我建议你在纸上亲手动一遍因为在面试时能边写代码边把推演过程讲清楚是绝对加分项。下面我把上面的 Python 最优解对输入 [1, 2, 3, 4] 每一步都列出来。先看第二步从左往右填充左边乘积初始 ans [1, 1, 1, 1]i 1ans[1] ans[0] * nums[0] 1 * 1 1i 2ans[2] ans[1] * nums[1] 1 * 2 2i 3ans[3] ans[2] * nums[2] 2 * 3 6。此时 ans [1, 1, 2, 6]这个数组暂时表示“每个位置左边的乘积”。再从右往左乘右边乘积suffix 初始为 1i 3ans[3] 6 * 1 6然后 suffix 1 * nums[3] 4i 2ans[2] 2 * 4 8然后 suffix 4 * nums[2] 12i 1ans[1] 1 * 12 12然后 suffix 12 * nums[1] 24i 0ans[0] 1 * 24 24然后 suffix 24 * nums[0] 24。最终 ans [24, 12, 8, 6]完全正确。我强烈建议你把这几步亲手写一遍尤其是 i 2 那一步感受一下 suffix 从 4 变成 12 之后再被拿去乘 ans[1]体会“右边乘积”这个状态是怎么被一路维护下来的。3.3 三种复杂度方案对比解法时间复杂度额外空间评价暴力双重循环O(n^2)O(1)逻辑简单一定超时左右乘积数组O(n)O(n)可通过但不够优雅复用输出数组O(n)O(1)面试满分答案从代码量上看最优解和次优解只差一个数组但思路完全是两个层级。很多算法题的提升路径就是这样的先保证做对再考虑少用点空间最后把代码写得既简洁又容易讲清楚。除自身以外数组的乘积恰好是这条路径的教科书式例子。4. 边界条件与多语言实现避坑指南4.1 数组里有 0除法解法崩溃本解法从容前面提过如果允许用除法遇到 0 会非常麻烦。我在这里系统地把 0 的情况列一下方便你面试时万一被追问。假设数组里有一个 0比如 [0, 1, 2]。正确答案是 [2, 0, 0]因为位置 0 的答案是 1 × 2 2其余位置都因为乘了 nums[0] 0 而变成 0。如果你非要用总乘积除以当前数的思路就得先统计 0 的个数0 的个数大于等于 2 时答案数组全是 00 的个数等于 1 时只有 0 所在位置是非零答案没有 0 时才能直接用除法。这套 if-else 虽然能写出正确代码但显然不优雅。而前缀积乘后缀积的解法从头到尾只做乘法0 参与乘法自然得到 0根本不需要特判。这正是题目设计者的心机看起来是考数学实际是考数据结构的稳健性。你可以把“乘法的稳健性”写进面试答题里这句话会让面试官觉得你确实理解了解法之间的本质差异。4.2 空数组、单元素、负数和大数溢出虽然 LeetCode 原题一般保证数组长度大于等于 2但写代码时养成防御习惯没有坏处。长度为 1 时除自己外没有其他元素答案应该是 [1]长度为 0 时理论上是空数组。正规解法里 ans 初始化为 [1] * n空数组时循环根本不执行返回 []单元素时返回 [1]恰好都是对的这算是一个不错的隐形福利。负数不需要额外处理因为乘法符号自动管理负负得正结果和正数没有本质区别。你只需要注意别把“乘积结果”和“当前值”混在一起判断。大数溢出则要根据语言区分处理。C 的 int 只有 32 位数组乘积很容易超出范围实际工程里建议中间计算用 long long最后根据题目要求决定要不要取模。Python 的 int 是任意精度刷题阶段完全不用担心溢出问题。Java 的 int 和 C 类似也要留意。这也是为什么很多题解的中间变量习惯写 long就是为了避免极端用例爆掉。4.3 多语言实现的细节差异C 写这道题最大的坑在于 n 的类型是 size_t它是个无符号整数。如果你把循环写成for (int i n - 1; i 0; --i)当 n 0 时 i 初始为 -1但循环条件 i 0 在无符号比较下会变成 true导致严重越界。正式代码中可以先用int n nums.size()转换或者干脆在函数开头判空保证 n 至少为 1就能避开这个坑。Python 里[1] * n看起来舒服但要知道它创建的是同一个整型对象的引用列表。int 是不可变对象所以这里没问题如果列表元素换成可变对象比如[[0] * m] * n就会踩到引用共享的大坑。范围遍历range(n - 1, -1, -1)的写法要记牢第三个参数 -1 表示倒序步长少了它就会写成range(n-1, 0, -1)导致漏掉 i 0 的位置。Java 和 C# 数组默认初始化为元素类型的默认值int 数组初始全是 0。如果直接用默认数组再乘结果会全部变成 0。所以必须显式填充 1Java 可以用Arrays.fill(ans, 1)C# 可以直接循环赋值或者用Enumerable.Repeat(1, n).ToArray()快速生成但要明白它其实是构造了一个新的序列内部会有额外开销。顺带说一句网上搜这道题时常会关联出“数组指针和指针数组”“C 语言指针数组存放字符串”这些内容。它们在 C/C 语境下是很好的基础题但和本题的解法没有直接关系。如果你是为了准备面试建议把 C 的数组、指针、引用的基本关系搞清楚即可不必在这个衍生话题上花费太多时间。5. 从这道题延伸出去数组类题目的通法5.1 前缀积和区间查询的套路关系除自身以外数组的乘积本质上就是“前缀积乘后缀积”。而这个思想不仅仅是这题的专属它和“前缀和”构成了一对双胞胎。前缀和的经典应用是快速求任意区间 [l, r] 的和做法是维护一个前缀和数组 S区间和等于 S[r1] - S[l]。前缀积的数学形式也类似区间 [l, r] 的乘积等于 P[r1] / P[l]其中 P[i] 表示 nums[0..i-1] 的乘积。只不过除法在数组存在 0 时不安全所以实际工程里会换用分段处理或者加一个特判。从这个角度看LeetCode 的数组题其实是可以分类学习的。前缀和、前缀积、差分数组、滑动窗口、双指针、原地修改每类背后都有固定的思路模板。你把这题当成“前缀积 原地修改”的交叉点来复习记忆效率会比单纯背题解高很多。5.2 刷题路线这题做完接着做哪些如果你刚把这道题彻底消化掉我建议顺手刷几个关联题巩固LeetCode 53 最大子数组和练的是扫描过程中维护中间状态LeetCode 303 区域和检索练的是前缀和模板LeetCode 724 寻找数组的中心下标可以看作这题的降级版只需要单侧乘积信息LeetCode 560 和为 K 的子数组则是前缀和加哈希表的组合拳。每刷完一题我会在题解旁边的空白处用一句话总结它的核心思路。比如这题写的是“每个位置 左边乘积 × 右边乘积”“边界用空积 1”。这个方法听起来笨但当你刷到第二十题、第三十题时翻看这些一句话笔记会发现自己已经能把不同题串成网络。这是我刷题两年多以来亲测最有效的沉淀方式。5.3 常见误区与小建议汇总第一个误区是把 suffix 更新顺序搞反。这是最高频的错误没有之一。只要你在循环里先更新 suffix 再乘到 ans[i]整道题就从“除自己以外”变成了“包含自己”。第二个误区是数组初始化成 0Java 和 C# 尤其容易踩一个 Arrays.fill 能解决的事别让它在面试现场翻车。第三个误区是以为还有复杂度更优的解法。实际上 O(n) 时间和 O(1) 额外空间就是这道题的理论极限因为你必须看每个元素至少一次也至少需要返回 n 个结果。最后分享一点个人体会。我自己第一次做这道题也是先想到除法被禁掉之后愣了好一会儿最后看了题解才明白前缀积乘后缀积的精髓。后来面试别人我特别爱问“为什么从右往左要先用 suffix 乘答案再更新 suffix”这一句基本就能分辨出对方是背题还是真懂。如果面试时你会紧张我建议你在白板上先把 [1, 2, 3, 4] 的中间过程写出来再动笔写代码这样推导思路顺手代码也不容易出错。这道题值得你反复刷三遍每一遍都会对数组遍历有更深的体会。