如果你刷过LeetCode Hot 100大概率绕不开这道“除自身以外数组的乘积”。我第一次做这道题时第一反应是把整个数组乘一遍得到总和然后每个位置除以它自己不就完事了吗结果题目直接封死了这条路——明确要求不能用除法。这一刀切下来不少刷题的人就卡在门口原因不是不会写循环而是对“能不能用除法”背后真正想考的东西没想透。这道题之所以能在Hot 100里长期占一个位置它并不是在考你某个高深的算法而是在考一类非常基础、但工程里经常出现的思维模式如何在一个序列上只用当前元素周围的信息以线性时间完成计算并且尽量不占用额外空间。这篇文章就从一个实际刷题的人视角把这道题的完整思考链路拆开讲从暴力解为什么不行到前缀积/后缀积怎么想出来再到空间复杂度怎么压到O(1)最后说说我在笔试面试里踩过的坑和总结出的小经验。1. 这道题到底在考什么约束信息比答案本身更值钱很多题解上来就直接贴代码但我觉得搞懂“出题人为什么这么设计”比记住代码重要得多。这道题的原题描述很简单给定一个整数数组nums要求返回一个新的数组answer其中每个answer[i]等于原数组中除nums[i]之外其余所有元素的乘积。但题目里嵌了三个很不起眼、却决定了整个解题方向的约束。1.1 一个“看似简单”的题目为什么能反复刷你如果只看功能描述会觉得这道题是Easy难度无非就是双层循环每个位置把除了自己以外的数乘一遍。但LeetCode把它放在Hot 100里还标成Medium是因为真正拉开差距的是后半句话“请不要使用除法且在O(n)时间复杂度内完成。” 这句话直接把最简单的两条路堵死逼着你去想另一种分解方式。我在面试中也经常把这道题当“试金石”因为候选人的第一反应往往最能暴露思维习惯。有人立刻开始考虑数组里有几个零、除零怎么办这种人是“条件反射型选手”但容易跑偏有人沉默十几秒后说“可以用左边乘积乘右边乘积”这种人已经逐渐养成“把约束当线索”的习惯是更有工程潜力的一类。1.2 三个约束条件逐字拆解这道题的约束不是随便写上去的每一条都在帮你排除错误答案也在暗示正确方向。我梳理了一下“不能用除法”这是最硬的一条约束。它把“总体乘积除以自身”这个最直觉的方案否决掉逼你放弃全局视角转向局部信息的组合。想一想如果允许除法这道题就退化成一个乘法和一个除法循环Medium名不副实。“O(n)时间复杂度”这句话排除了双层循环的暴力解。同样它也在暗示你一个位置只需要扫一遍就能获得答案关键是“如何只扫一遍的同时保住左右两侧的信息”。“输出数组不计入空间复杂度”很多新手没注意到这条但它是Follow-up题目里能降低额外空间的关键依据。正因为返回的那个数组不算额外空间你才能放心地在answer上“边写边用”。从我刷题的经验看把这三条约束翻译成人话就是你只能线性扫描不能做除法但你可以借用返回数组本身来省空间。看到这三条约束时脑子里应该立刻浮现出“前缀积”“后缀积”这两个词。2. 三条常规思路的真实表现暴力、除法与它们的致命伤在进入正确解法之前我先把放在面前的几条“错误路径”跑一遍。不是说它们全错而是它们各自有致命的短板。理解这些短板的成因反而能帮你理解为什么最终的标准解法长那个样子。2.1 暴力解法正确但注定超时的两重循环暴力解法是最符合直觉的实现def product_except_self(nums): n len(nums) res [1] * n for i in range(n): for j in range(n): if i ! j: res[i] * nums[j] return res这个解法逻辑完全正确但存在两层循环整体时间复杂度是O(n²)。当n到10⁵量级时运算次数是10¹⁰跑一次要几十秒。LeetCode的评测环境根本不会给你跑完的机会。所以暴力解唯一的用途是在小规模测试上辅助验证正确解。你自己写题的时候可以留这么一个朴素的版本拿随机数据对拍确认优化后的代码没有逻辑错误。我在实际刷题时经常拿这种“笨方法”当基准器。2.2 除法解法被“零”一票否决的贪快方案再来看我开头那个“聪明”方案def product_except_self_division(nums): total 1 for v in nums: total * v return [total // v for v in nums]没有0的时候这代码能用也很快。但一旦数组里出现0事情就变得极其尴尬。假如数组中有一个0那么除了这个0所在的位置外其他位置的结果全都得是0只有0那一位的答案是“剩下所有非零元素的乘积”。如果有两个或以上的0整个结果数组的所有位置都是0。把这种分支逻辑完整写出来你会发现它并不比前缀积法简单def product_except_self_division(nums): n len(nums) zero_count nums.count(0) if zero_count 2: return [0] * n total 1 for v in nums: if v ! 0: total * v res [] for v in nums: if zero_count 1 and v ! 0: res.append(0) elif zero_count 1 and v 0: res.append(total) else: res.append(total // v) return res你发现问题了吗为了让除法方案适配“有0”的场景代码的复杂度和分支数量已经开始接近甚至超过前缀积法了。更不用说当数组中存在很大的整数时总乘积可能会突破int的范围而如果把所有元素的乘积算出来再做除法中间的临时数值可能会大到溢出。数据稍有极端情况这个方案随时会翻车。这也是工程中“看似捷径实则脆弱”的典型代表。2.3 被误导的Log解法精度和0陷阱的双重灾难我见过网上有些帖子说既然乘法有交换律那把每个数取对数把乘法转成加法最后再用exp还原岂不美哉听起来很妙但实际操作你就会发现一堆问题log(0)在数学上无定义数组一旦含0整个方案当场失效浮点数的精度有限大数取对数再还原误差会被放大LeetCode要求的整数结果很容易差一两个数最后还要做四舍五入或取整边界情况多得让人头疼。这个方案没有任何实际竞争力我提它只是想让大家明白算法题里的优化必须建立在精确运算和清晰分支的基础上任何“取巧”绕过约束的方式最后往往会被更复杂的问题反噬。3. 左右乘积法把答案拆成“左边×右边”现在进入正题。前面几条路都走不通之后我们会得出一个关键结论每个位置的答案其实可以拆成两个部分——左边所有元素的乘积乘以右边所有元素的乘积。这就是标准解法“前缀积×后缀积”的来源。3.1 从一个直觉到一类题为什么“前缀信息”重要很多人觉得“左边乘积乘右边乘积”这个想法很突兀像是魔术师变出来的。实际上它不是凭空出现的而是来自一个非常基础的问题重构对于下标i题目要的是 nums[0] × nums[1] × … × nums[i-1] × nums[i1] × … × nums[n-1]。这个表达式里恰好缺少的是nums[i]本身。你会发现这个式子天然分成了两截下标i之前的所有数连乘和下标i之后的所有数连乘。前者就是“前缀积”后者就是“后缀积”。前缀和、前缀积这类思想本质上都是在说在数组上从左到右扫一遍时把已经路过的信息累积起来存好之后每个位置都可以O(1)地取到自己需要的“历史信息”。你后面刷“接雨水”“最大子数组和”“连续子数组乘积”之类的题会反复遇到同一个模式。把这道题的原理吃透等于给这一类题都打了底子。我自己的感受是前缀积的思路一旦想通你会瞬间理解“为什么不允许你用除法”。因为不用除法也能通过组合两次扫描的结果得到和除法一样的效果而且中间不会出现“除数为0”的坑。结构的对称性让这个解法非常稳健。3.2 用两个数组实现的最清晰版本最直观的实现方案是准备两个数组一个left数组记录每个位置左侧所有数的乘积一个right数组记录每个位置右侧所有数的乘积。然后answer[i] left[i] * right[i]。具体步骤分解如下初始化left[0] 1因为第一个元素左边没有任何数空乘积记为1。从左到右遍历left[i] left[i-1] * nums[i-1]。从右到左遍历right[n-1] 1同理为空乘积。right[i] right[i1] * nums[i1]。最后answer[i] left[i] * right[i]。写成代码就是这样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[i1] * nums[i1] res [1] * n for i in range(n): res[i] left[i] * right[i] return res三个循环都是线性扫描时间复杂度O(n)额外开辟了两个长度为n的数组空间复杂度O(n)。这个版本胜在逻辑清晰、不容易写错也是我建议新手先熟练掌握的版本。3.3 为什么这个解法在面试中很加分我面试别人时如果候选人能写出这个版本我一般会继续追问一句“你觉得额外空间还能不能省”这个追问本身就是在考察两件事你是否理解题目中“输出数组不计入空间复杂度”这句话的含义你是否具备“复用内存”的工程意识。写出双数组版本只是第一步面试官真正想看到的是你从“能解”走向“优雅地解”。裁员潮过后很多公司更在意候选人在有限资源和内存下写高质量代码的能力这道题的Follow-up恰恰就是这种能力的微缩模型。4. 从O(n)空间到O(1)Follow-up的完整落地LeetCode这道题后面有一个很关键的Follow-up能不能在O(1)的额外空间复杂度内完成注意很多新手会卡在这句话上因为不清楚“输出数组里存东西算不算空间”。4.1 复用输出数组先存前缀积题目明确说过输出数组不计入额外空间。所以我们可以大胆地把answer数组作为“临时存储区”第一阶段只存前缀积。此阶段answer[i]的含义临时变成原数组nums中下标i左侧所有数的乘积。def product_except_self(nums): n len(nums) res [1] * n # 第一遍res[i] nums[0] * ... * nums[i-1] for i in range(1, n): res[i] res[i-1] * nums[i] return res等等如果只读上面这段代码你会发现res[i]存的是nums[0]到nums[i-1]的乘积这就是左前缀积。写的时候要注意res[i-1]已经是左侧乘积所以res[i] res[i-1] * nums[i-1]但上面的代码里写的是nums[i]这是不对的。下面是修正后的写法。def product_except_self(nums): n len(nums) res [1] * n # 第一遍res[i] nums[0] * nums[1] * ... * nums[i-1] for i in range(1, n): res[i] res[i-1] * nums[i-1] return res因为res[0] 1表示第一个元素左边没有元素res[1] res[0] * nums[0] nums[0]res[2] nums[0] * nums[1]以此类推res[i]恰好是下标i之前所有数的乘积。这个阶段的res数组已经把“左边”的信息完整存下来了。4.2 一个变量搞定后缀积倒序遍历的妙处左前缀积准备好之后还差右后缀积。如果再用一个数组去存右后缀那额外空间又是O(n)。但实际上我们完全不需要把右后缀全部存下来因为最终每个answer位置只会用一次右后缀值直接用变量滚动更新即可。用一个变量R表示“当前下标右侧所有数的乘积”。开始时R 1因为最右边的元素右侧没有任何数。接着从右往左遍历对每个下标i把res[i]乘上R这一步把“左侧乘积”和“右侧乘积”组合成最终答案更新R R * nums[i]让R变成下一个下标i-1对应的右侧乘积。def product_except_self(nums): n len(nums) res [1] * n for i in range(1, n): res[i] res[i-1] * nums[i-1] R 1 for i in range(n-1, -1, -1): res[i] * R R * nums[i] return res我手动跑一个例子更好理解假设nums [1, 2, 3, 4]第一遍循环后res[0] 1因为它是空积res[1] nums[0] 1res[2] 1 * 2 2res[3] 2 * 3 6所以res [1, 1, 2, 6]它存的就是每个位置左侧的乘积。第二遍从右往左i3时res[3] 6 * 1 6R更新为1 * 4 4i2时res[2] 2 * 4 8R更新为4 * 3 12i1时res[1] 1 * 12 12R更新为12 * 2 24i0时res[0] 1 * 24 24R更新为24 * 1 24最终res [24, 12, 8, 6]和题目预期完全一致。这个过程中除了返回的res数组我们只用一个R变量额外空间是O(1)。时间复杂度仍然是O(n)而且只遍历了两遍数组稳定性很好。4.3 容易写错的三个细节这个解法代码很短但有几个细节我每次讲解时都要强调因为它们全是我在真实笔试里见过别人踩过的坑res[i]的赋值时机先乘R再更新R。顺序如果搞反虽然第一层循环的res左边部分不受影响但最终的组装结果就会错因为R已经包含了nums[i]本身的乘积乘进去就变成“包含自身”的结果了。R的初始值必须为1它代表了“右侧什么都没有”时的空积数学上要求是1。如果有人把初始值设成0或nums[n-1]那结果会全盘错掉。边界元素不要单独特殊处理res[0]的最终答案是“全数组乘积除以nums[0]”它在倒序遍历时第一次就会被乘上R不需要额外写if。新手很容易手痒加一个“if i 0就跳过”的分支反而画蛇添足。5. 实战中的边界、语言细节与面试节奏写到这里题目本身的最优解已经出来了。但我觉得一篇有价值的博文不能停留在这因为实际做题和笔试面试时还有很多“题解里看不到、却很容易扣分”的细节。我把这些年积攒下来的几个关键经验一并写出来。5.1 一个容易被忽视的坑0的分布决定了你对解法的信心现在你知道了O(1)空间的标准解法但当数组里有0时这个解法依然成立不需要任何分支。这是它最大的优势。我在牛客和LeetCode评论区经常看到有人问“如果有0怎么办” 标准答案就是根本不需要特殊处理因为前缀积和后缀积的组合天然避开了除以0的问题。如果面试官额外让你“允许使用除法但要求结果数组里每个位置仍然不能包含自身”那就是另一道题了。此时你要先数0的数量0个0时直接除1个0时除0位置外全为0只有该位置是其余数乘积2个0及以上则答案全为0。我把这个分支写出来是希望大家明白一旦允许除法反而要做更多边界判断。这也从侧面证明了题目的约束是在帮你规避复杂性。5.2 多语言实现的差异与注意点不同语言写这道题时有三个隐藏细节值得留意Python整数不会溢出你不用担心乘积越界但这道题通常数据范围不大所以也没有性能问题建议平时用Python刷题练习时重点理解“R变量滚动更新”的思路别只停留在双数组版本。C要留意int型可能溢出。LeetCode原题数据范围是32位有符号整数范围内的乘积和但如果你在笔试时用int遇到极端数据可能爆掉。稳妥起见中间累积量可以用long long返回前再转回int。Java和C类似int乘法可能溢出实战中建议用long做累积最后再转回int数组。我贴一份Java版的参考public int[] productExceptSelf(int[] nums) { int n nums.length; int[] ans new int[n]; for (int i 0; i n; i) { ans[i] 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; }5.3 面试时的推进节奏先从哪个版本说起很多候选人会犯一个策略性错误一上来就写最优解然后被追问“为什么这么想”时反而讲不清楚。我更推荐按照“暴力→双数组→O(1)空间”的顺序展示思路。这样做有几个好处面试官能看到你的思维推导过程知道你是在理解问题的基础上优化而不是背了模板暴力解和双数组解都更容易解释清楚如果最优解直接写中间的关键跳跃需要很强的表达力才能兜住万一最优解某个细节写错你还能退回到双数组版本降低整题崩盘的风险。我自己的习惯是这样的拿到题先复述约束条件说“题目要求不能用除法且时间O(n)我想到可以用前缀积和后缀积组合”然后先快速写双数组版本确认正确后主动和面试官说“这里我可以进一步把空间复杂度降到O(1)因为输出数组不计入额外空间”再翻新成滚动变量版本。这个节奏在面试中非常加分既展示实力也展示沟通习惯。另外要记住面试官问你“还有没有更好的解法”时不代表现在的解法是错的而是在考察优化意识。你可以先明确说“当前方案已经是最优时间复杂度O(n)、最优空间O(1)因为在数组遍历类问题里至少需要访问每个元素一次复杂度下界是O(n)”这句话能把一道“会做”的题提升到“理解得很深”的层次。5.4 从这道题延伸出去的考法这类“前缀后缀”的思维框架在LeetCode周赛和Hot 100里反复出现。我随手就能列出几道关联题前缀和类比如“和为K的子数组”“区域和检索”核心也是线性扫描时保存历史信息接雨水每个位置能接多少水取决于左侧最大值和右侧最大值的较小者和这道题的双侧遍历思路如出一辙除自身以外数组的和如果前端开发或数据分析岗面试有时会出这种变形思路完全一样把乘法换成加法即可乘积最大的子数组虽然结果要求的是连续子数组的最大乘积但同样用“维护到当前位置为止的最大值和最小值”来规避负数翻转的坑思想都是“滚动状态边界转换”。我目前也在刷LeetCode周赛题越来越觉得很多难题就是“把基础题型的思路叠加再叠加”。如果你把这道题的“前缀积/后缀积”练到肌肉记忆水平遇到类似问题就能省下大量思考时间。最后说几句实战心得写完这段踩坑记录我再分享一个我自己的体会很多时候决定一道题能不能快速解出来的关键不是你会多少个算法而是你能不能在读题时抓住约束条件背后的暗示。这道题把“不能用除法”写在脸上等于直接告诉你“去组合局部信息”。如果你能形成这种条件反射刷题效率会明显提升一个档次。我建议拿到这道题以后不要只看题解就觉得自己会了。你可以在本地IDE里从暴力解开始重写一遍每跑一步都打印中间数组用随机大数组测一测性能差异再手动运行几个包含0的极端案例。手动跑通一遍的收获比看十遍题解都大。方法上我习惯用一个小的nums [1, 2, 3, 4]把前缀积和后缀积在草稿纸上一步一步算出来再对照代码里的循环变量变化这样能最直观地看清答案是怎么“组装”出来的。这道题还有一个让我印象很深的地方它在LeetCode Hot 100里经常被当作“前50题”的标志因为刷到这道题时恰恰是很多人从“会写代码”向“会设计算法”转变的节点。花一晚上把它吃透比稀里糊涂刷完十道题要值太多。希望这篇拆解能帮你真正迈过这道坎。