刷 LeetCode 的人应该都有这种感觉有些题第一眼看过去觉得这不就是求个乘积吗然后动手一写才发现处处是坑。除自身以外数组的乘积LeetCode 238Product of Array Except Self就是这么一道题。它在 LeetCode 热门 100 题里常年占着一个位置看起来是小学算术题——给我一个数组我返回一个新数组每个位置放的是除了它自己以外所有元素的乘积。但题目末尾加了一行不能使用除法并且要在 O(n) 时间内完成。就这一行字直接让无数人的第一个版本写出来就废掉。这篇文章就是写给正在刷题、准备面试的同学。我会把这道题的完整思考链路讲透从暴力解为什么不行到前缀积/后缀积的核心原理再到空间 O(1) 的优化写法最后聊多语言实现里那些容易踩的坑。不是单纯贴一份能通过的代码而是把为什么这么写讲明白。这样你在面试里被追问任何变体都能接得住。1. 除法被禁之后这道题的难度直接跳了一档1.1 题目到底问的是什么先说清楚题目本身。给定一个整数数组nums要求返回一个数组answer其中answer[i]等于原数组中除nums[i]以外所有元素的乘积。举个例子输入[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看着是不是很简单真正动手写的时候限制条件才是主角不能用除法时间复杂度要求 O(n)并且通常还要求空间 O(1)输出数组不算额外空间。LeetCode 的题目说明里有一个保证所有前缀乘积和后缀乘积都在 32 位整数范围内所以不用考虑大数溢出到任意精度的问题——这个保证很重要后面我会专门说。很多第一次做这道题的人会想先算整个数组的乘积然后每个位置用总乘积除以当前元素不就行了然后一看题目禁止使用除法。OK那用减法当然更不可能。为什么题目非要把除法禁掉因为一旦允许除法这道题就退化成一个乘法加一个除法没有任何算法训练的价值。出题人想让你意识到除自身以外的乘积这件事本质上可以被拆解成左边的乘积乘右边的乘积而这两部分都可以通过一次遍历提前算好。1.2 暴力解为什么当场被毙如果你完全不管复杂度最直接的暴力写法就是两层循环对于每个位置 i遍历所有 j把j ! i的元素乘起来。代码大概长这样def product_except_self_bruteforce(nums): n len(nums) result [] for i in range(n): prod 1 for j in range(n): if j ! i: prod * nums[j] result.append(prod) return result这个解法的时间复杂度是 O(n^2)。当 n 是 10、20 的时候无所谓但 LeetCode 上这道题的数组长度上限是 10 万级别O(n^2) 意味着要执行百亿次乘法直接超时。更关键的是它完全没有利用到乘积这个运算本身的可组合性属于纯枚举思路——面试官看到这个答案基本就不会让你通过了。那能不能先求总乘积再逐个除可以但开头就说了除法被禁止。而且即使没有这个禁令除法方案在数组含 0 的情况下也会翻车比如数组是[0, 1, 2]总乘积是 0你拿 0 去除 0得到的是NaN或者异常而不是正确结果。所以这条路从一开始就堵死了。到这里你大概能感受到这道题的张力它明明和乘积有关但你不能用最省事的除法它要求快但你又不能对每个位置单独扫一遍。于是唯一合理的思路就是把信息预处理好。2. 前缀积与后缀积把除自身拆成左半边乘右半边2.1 两个辅助数组的朴素版本假设我有两个数组left和rightleft[i]表示nums[0]到nums[i-1]的乘积也就是 i 左侧所有元素的乘积。right[i]表示nums[i1]到nums[n-1]的乘积也就是 i 右侧所有元素的乘积。那么answer[i] left[i] * right[i]一句话就解决了。问题变成怎么高效地填满left和right。left的填充逻辑是一个很经典的递推left[0] 1 # 第一个元素左侧没有元素乘积定义为 1 for i in range(1, n): left[i] left[i - 1] * nums[i - 1]right的填充逻辑对称right[n - 1] 1 # 最后一个元素右侧没有元素乘积定义为 1 for i in range(n - 2, -1, -1): right[i] right[i 1] * nums[i 1]两个数组都只遍历一遍O(n) 时间最后再遍历一遍计算答案。整体时间 O(n)空间 O(n)。用 Python 写出来大概是这样def product_except_self(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)]这个版本能通过 LeetCode 的所有测试用例也是理解这道题的最佳起点。我不建议一上来就背空间优化版本先把两个辅助数组的逻辑写透你才知道后面每一步优化到底省掉了什么。2.2 为什么这个套路能成立这个套路背后的数学直觉很朴素乘法是独立作用于每个位置的。要求某个位置自身以外的乘积你可以把这个全体乘积按位置切开左边一段、右边一段各自求乘积再乘起来。中间那个元素本身根本没有参与计算。用生活化的例子理解假设你是一个排球教练要统计每个队员的队友总贡献值即除了他自己之外全队的得分总和。你不会去把每个人从他自己的统计里剔除而是先算左半区队友的总得分、右半区队友的总得分然后把两段加起来。这里加法对应乘法位置 i 对应被剔除的那个人。这个套路在算法里叫前缀/后缀思想。前缀积、前缀和、后缀最大值都是同一个家族。一旦你意识到某个位置的答案 它之前的信息 组合 它之后的信息很多题都会豁然开朗。LeetCode 上大量题目都是这个套路比如接雨水、股票买卖、左右乘积数组等。所以这道题虽然叫乘积它真正的考点是预处理与信息组合而不是乘法本身。3. 空间 O(1) 优化用一个输出数组走两遍3.1 第一遍从左往右记录左侧乘积既然answer[i]本来就是我们要返回的东西能不能直接把它当left数组用当然可以。第一遍从左往右让answer[i]存下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]这一步做完answer数组里存的是answer[0] 1 answer[1] nums[0] answer[2] nums[0] * nums[1] answer[3] nums[0] * nums[1] * nums[2] ...也就是说answer[i]已经是左侧乘积了。但此时它缺少右侧的信息不能直接返回。3.2 第二遍从右往左乘上右侧乘积第二遍遍历从右往左维护一个变量right它表示当前已经扫过的右侧元素乘积。初始时right 1因为最右侧的位置右边没有元素。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第二遍循环里每步做的事answer[i] * right把已经算好的左侧乘积乘上右侧累计乘积得到完整答案。right * nums[i]把当前元素吸收进右侧累积里供左边下一个位置使用。拿[1, 2, 3, 4]走一遍全过程第一遍后answer [1, 1, 2, 6]分别对应左侧乘积。第二遍从i 3开始right 1i 3answer[3] 6 * 1 6然后right 1 * 4 4i 2answer[2] 2 * 4 8然后right 4 * 3 12i 1answer[1] 1 * 12 12然后right 12 * 2 24i 0answer[0] 1 * 24 24然后right 24 * 1 24最终answer [24, 12, 8, 6]和预期完全一致。这个版本的时间复杂度还是 O(n)但额外空间只有 O(1)——right变量是常数空间answer是题目要求返回的输出数组LeetCode 的约束里明确说输出数组不计入空间复杂度。所以这是这道题的标准最优解。3.3 一个容易绕晕的索引细节我在辅导别人做这道题时发现大家最容易出错的地方不是整体思路而是第一遍循环的边界。写第一遍时你要回答一个关键问题answer[0]应该等于多少它的左边没有元素按乘积的幺元定义空乘积等于 1所以answer[0] 1。然后从i 1开始用前一位置的左侧乘积乘上前一位置的元素即answer[i] answer[i - 1] * nums[i - 1]。这里有个容易搞混的点为什么乘的是nums[i - 1]而不是nums[i]因为answer[i]表示不包括自己的左侧乘积所以它应该继承answer[i-1]即更左边所有元素的积再乘上紧挨着自己的左边那个元素nums[i-1]。如果写成nums[i]那就把自己也算进去了后面答案全部错位。第二遍的边界同样要注意right初始化为 1而不是nums[n - 1]。因为最后一个位置的右侧没有元素空乘积是 1。然后从右往左推进right才逐步吸收nums[n-1]、nums[n-2]等。如果把right初始化成nums[n - 1]那answer[n - 1]会多乘一个自身错得离谱。这些边界细节就是面试官最爱深挖的地方。你不仅能写出代码还能讲清楚为什么这里从 1 开始为什么这里乘前一个元素这道题才算真正过关。4. 边界条件和面试官追问零、溢出、单元素4.1 数组里出现 0 会怎样这是除自身以外数组的乘积最经典的干扰项。如果用除法方案数组里有 0 会立刻出问题总乘积是 0任何total / nums[i]在nums[i] 0时都是除以零程序直接抛异常。就算你强行处理单零的情况也要分有一个 0有多个 0多种情况代码变得非常丑陋。而前缀积/后缀积方案天然免疫 0 的问题因为每个位置的答案只依赖左侧和右侧的乘积而这些乘积如果包含 0结果就是 0没有任何需要特殊判断的逻辑。举个例子nums [0, 1, 2, 3]答案应该是[6, 0, 0, 0]。你可以手动验证一下前缀/后缀方案能不能算出来第一个位置左侧为空1右侧乘积是 6所以答案是 6第二个位置左侧乘积是 0右侧乘积是 60 乘 6 还是 0没问题。所以这道题表面上有 0 的陷阱但正确算法根本不需要为 0 写分支。这正是不用除法的另一个强大理由。4.2 空数组与单元素数组怎么处理LeetCode 原题的约束是nums.length 2所以正常情况下不会给你空数组或单元素数组。但面试官有时候会故意问你自己实现一个通用一点的版本要不要考虑 n 等于 0 或 1 的情况先说单元素数组比如nums [5]。按照题面answer[0]应该是除 5 以外所有元素的乘积但除了 5 之外一个元素都没有这个值定义成多少严格数学上空乘积约定为 1所以answer [1]。你看上面的 O(1) 代码n 1时第一遍循环range(1, 1)直接不执行answer [1]第二遍i 0时answer[0] * 1然后right * 5最终返回[1]——正好是对的不需要单独处理。空数组呢nums []时答案也是空数组。但 C/C 写法里要注意n - 1会变成-1如果n是无符号整数这就是个灾难。所以我一般会在函数开头加一个防御性判断如果长度为 0 或 1直接返回原数组的空乘积版本。这不会影响 LeetCode 的提交但能让你的代码在面试中显得更严谨。4.3 如果允许用除法这道题反而更麻烦很多人会好奇既然除法不让我用那我先算总乘积再逐个除到底哪有问题除了性能其实没问题O(n)主要问题就是 0 的处理。假设允许除法数组是[0, 1, 2]总乘积 0answer[0] 0 / 0无法计算如果数组是[1, 0, 2]总乘积 0answer[1] 0 / 0还是无法计算如果数组是[0, 0, 2]总乘积 0answer[0] 0 / 0无法计算answer[1] 0 / 0无法计算唯一能正确计算的情况是数组里一个 0 都没有。所以除法方案需要先统计 0 的个数然后分三种情况讨论没有 0、一个 0、多个 0。这么一来代码的复杂度和出错率远高于前缀/后缀方案。出题人禁掉除法既是在考察你的算法思维也是在帮大多数做题人避开这个多分支的泥潭。这也提醒你一个通用经验当一道题禁止你使用某个看起来很自然的操作时通常不是因为它简单而是因为它会引入额外的坏味道。你要做的不是想方设法绕过禁令而是理解禁令背后真正希望你掌握的数据关系。5. 用 JS、Python、C、C 各写一遍的踩坑记录5.1 JavaScript数组方法看着好用但别在循环里用 splic这道题在 JS 里有很多种写法最直观的是reduce求总乘积再map返回但一旦你这么做就掉进了除法陷阱。真正推荐的做法是上面那个两遍遍历JS 代码如下var productExceptSelf function (nums) { const n nums.length; const answer new Array(n).fill(1); for (let i 1; i n; i) { answer[i] answer[i - 1] * nums[i - 1]; } let right 1; for (let i n - 1; i 0; i--) { answer[i] * right; right * nums[i]; } return answer; };这里有一个 JS 特有的坑new Array(n).fill(1)和Array.from({ length: n }, () 1)都是安全的但new Array(n)如果你忘了.fill(1)里面的每个元素都是empty后面一乘就得到NaN。另外不要在循环里用splice来删除当前元素再求积因为splice本身是 O(n) 操作整个算法会退化到 O(n^2)一提交就是超时。还有一点JS 的数组方法是好用的工具但面试时我建议先写显式for循环把思路讲清楚。等面试官认可了再提一句也可以用更函数式的方式表达——比如用reduce生成前缀积数组。不要一上来写一些花哨的链式调用万一中途被问一句你这步时间复杂度是多少容易答不上来。5.2 Python切片和列表推导的注意点Python 版本最常见的就是我前面写的两遍遍历def product_except_self(nums): n len(nums) ans [1] * n for i in range(1, n): ans[i] ans[i - 1] * nums[i - 1] right 1 for i in range(n - 1, -1, -1): ans[i] * right right * nums[i] return ans这里有个 Python 初学者容易踩的坑切片会创建新数组。如果你写right_nums nums[::-1]然后对反转后的数组做累乘空间复杂度就变成 O(n) 了虽然 LeetCode 可能照样通过但面试官如果追问空间复杂度你就不占优势了。还有一个列表推导入门的坑[1] * n对于整数这种不可变对象是安全的因为每个位置的 1 都是独立的值。但如果你写[[1] * n] * m这里的* m复制的是外层引用你改一行会带着所有行一起变。这道题用不到二维数组但这个坑值得记一下因为你刷题早晚会遇到二维前缀和之类的题。Python 里还有一种比较隐晦的写法用itertools.accumulate生成前缀积from itertools import accumulate from operator import mul def product_except_self(nums): prefix list(accumulate([1] nums[:-1], mul)) suffix list(accumulate([1] nums[:0:-1], mul))[::-1] return [p * s for p, s in zip(prefix, suffix)]看起来非常简洁但可读性差而且accumulate本身也要 O(n) 空间。我实战中的建议是刷题写给人看的代码优先保证别人三秒能看懂简洁留给讨论环节再展示。5.3 C/Csize_t 与指针数组的经典坑C 版本直接拿vectorint写class Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint answer(n, 1); for (int i 1; i n; i) { answer[i] answer[i - 1] * nums[i - 1]; } int right 1; for (int i n - 1; i 0; --i) { answer[i] * right; right * nums[i]; } return answer; } };如果你把i声明成size_t无符号整数第二遍循环for (size_t i n - 1; i 0; --i)就会死循环因为无符号数永远大于等于 0i 减到 0 之后再减就变成SIZE_MAX循环根本停不下来。C 语言里用指针做这道题也会遇到同样的问题。C 语言版本还要手动管理内存int* productExceptSelf(int* nums, int numsSize, int* returnSize) { int* answer (int*)malloc(numsSize * sizeof(int)); *returnSize numsSize; answer[0] 1; for (int i 1; i numsSize; i) { answer[i] answer[i - 1] * nums[i - 1]; } int right 1; for (int i numsSize - 1; i 0; --i) { answer[i] * right; right * nums[i]; } return answer; }这里有个和热门搜索词里指针数组存放字符串指针数组移动指定位输出容易混淆的点。网上搜这道题的时候经常有人把指针数组的 C 语法题带进来实际上两者不是一个东西这道题是值类型数组的乘积指针数组是存放指针的数组完全是两回事。刷题的时候看到关键词数组指针别被带偏先确认题目在说什么数据结构。C 语言里还有一个从视觉上很难发现的坑malloc出来的内存没有初始化所以我在malloc之后直接给answer[0] 1然后循环里从 1 开始填这没问题。但如果你先写answer[i] 1的初始化循环再算就要确保所有位置都被赋值否则读未初始化内存可能返回任意值。6. 前缀思想不只是刷题从概率乘积到区间统计6.1 概率连乘下溢时的常规处理这道题刷完很多人的收获是前缀积原来可以这样用。但我想多说一句前缀积/前缀和的思想在真实业务里的出现频率远比想象中高。举个例子热门搜索词里有个概率乘积。很多推荐系统、风控系统里判断一个事件的整体概率需要把多个独立概率相乘比如转化率 点击率 × 加购率 × 支付率。当这些概率都很小的时候连续相乘很容易下溢为 0尤其用浮点数计算时。工程上常用的手段不是避免连乘而是把概率取对数连乘变成连加即log(P1 * P2 * P3) log(P1) log(P2) log(P3)。这和这道题里的前缀积思想很像你需要对一组数据做全局组合运算时可以先把中间结果缓存成前缀形式然后在任意位置用 O(1) 时间取出来。再比如你在做用户行为统计时经常要求某一段时间的累计值。如果每次都从头累加数据量一大就慢。正确做法是构建一个前缀和数组sum[i]表示前 i 条记录的总和那么[l, r]区间的总和就是sum[r] - sum[l - 1]。这就是前缀和的经典应用。把这层关系想清楚你就明白为什么 LeetCode 上会有那么多区间查询的题了。6.2 前缀和/前缀积在业务统计中的落地热词里还出现了树状数组树状数组模板动态数组。树状数组本质上是前缀和的进阶版它的核心操作就是维护前缀和并支持单点更新。当你的业务数据会频繁变动比如实时统计、实时排行静态的前缀数组就不够用了需要树状数组或线段树来动态维护前缀信息。你会发现在这些数据结构里前缀这个概念像地基一样反复出现。这道题的简单版本是提前把前缀积算好动态版本就是不得不考虑更新成本。不管哪个版本底层的思路都是一样的把每个位置的结果表达成某个前缀信息与其他信息的组合。所以刷题时别只满足于AC 了。花五分钟想想如果数组元素会动态变化这道题应该怎么改如果允许多次查询而不只是返回一个数组能不能用预处理加速这么一想你就从背题进阶到理解结构了。6.3 被禁用某操作时先想数据关系而不是硬刚最后说说不能使用除法这个限制给我的长期启发。现实中写业务代码经常遇到类似的约束。比如某个接口不允许用某种查询方法某个数据库不能用 join某个环境不支持某些内置函数。大多数人第一反应是找个替代方案把操作补回来但 LeetCode 238 教给我们的是另一条路当某个操作被禁时往往是因为你原本依赖的操作本身就不是最优路径数据之间可能存在更本质的关系。拿这道题来说除法之所以被禁表面上是为了防止 0 的出现深层原因是求除自身以外的乘积天然适合用左右组合来描述而不是用总体除去个体来描述。类似地当你在业务里发现某个操作受限先停下来想想能不能用前缀信息、增量更新、或者数据的某种守恒关系把问题重新表达一遍这往往能带来性能和代码质量的同步提升。我刷这道题刷过至少三遍每一遍都有新的体会第一遍学会了前缀/后缀数组第二遍掌握了空间优化第三遍才开始把里面的思想迁移到别的场景。如果你现在正卡在看得懂答案但自己写不出的阶段别着急。先把朴素的左右数组版本默写出来再一步步推到 O(1) 版本。等你能不看代码、只用纸笔完整推导出[24, 12, 8, 6]这个样例你的理解就到位了。面试前最后再提醒一句哪怕你代码已经背得滚瓜烂熟也要准备好解释为什么这里用 1 初始化为什么第二遍要从右往左如果数组很大但元素都很接近 0 会发生什么。这些追问才是这道题真正要考察的东西。