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 = 24
• answer[1] = 1 * 3 * 4 = 12
• answer[2] = 1 * 2 * 4 = 8
• answer[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 = 0
• answer[1] = 1 * 0 * 4 = 0
• answer[2] = 1 * 2 * 4 = 8
• answer[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^5，10^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[i+1] * ... * nums[n-1]

这正好等于：

前缀积（到i-1为止） 乘以 后缀积（从i+1开始）

如果用prefix[i-1]表示nums[0..i-1]的乘积，用suffix[i+1]表示nums[i+1..n-1]的乘积，那公式就是：

answer[i] = prefix[i-1] * suffix[i+1]

边界情况单独处理：

• 当i = 0时，prefix[i-1]不存在，此时左边没有任何元素，等价于乘 1，所以answer[0] = suffix[1]。
• 当i = n-1时，suffix[i+1]不存在，此时右边没有任何元素，等价于乘 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] = 24
• answer[1] = prefix[0] * suffix[2] = 1 * 12 = 12
• answer[2] = prefix[1] * suffix[3] = 2 * 4 = 8
• answer[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 ans

Java 版本：

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: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> 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。然后执行两步：

1. 先用当前right更新ans[i]。
2. 再把nums[i]乘进right，为下一个位置做准备。

如果反过来，先执行right *= nums[i]，再更新ans[i]，那么ans[n-1]就会多乘一个nums[n-1]，而ans[n-1]原本应该是“除自己外所有元素乘积”，多乘自己之后答案直接错了。

我用一个具体例子推演：nums = [1, 2, 3, 4]，正确写法下第二遍过程如下：

第一遍之后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 = 1，ans[0] *= 1结果为1，没问题。

另外题目说“所有元素乘积不会溢出 32 位整数”，这句话保证了中间变量乘到最大值时不会爆炸。但我自己在本地测试的时候，依然会把中间变量声明成long或int64，因为一旦你把这个解法搬到其他类似场景，输入数组可能全是10^9量级，连乘几个就会溢出。

4. 实操过程中真正容易踩的坑

4.1 除零陷阱与“不用除法”的深层原因

网上有很多人讨论“如果允许用除法和额外处理 0，能不能秒掉这题”。我直接说：能，但不推荐，原因有二。

第一，代码复杂度会上升。你需要统计 0 的个数：0 个 0，可以直接用总乘积除以每个元素；1 个 0，只有 0 所在位置的答案是总乘积，其他位置全是 0；2 个及以上 0，所有答案全是 0。这个分支逻辑写到代码里很容易漏，而且面试官一眼就能看出你还在依赖除法。

第二，除法和累乘的数值稳定性不同。Python 里整数除法要处理负数取整方向，C++ 里整数除法遇到 0 直接 UB，JavaScript 里1 / 0结果是Infinity，这些在刷题环境里都是雷。与其费劲处理各种语言特性，不如老老实实走前缀积路线。

我整理了一个对比表格，方便你直观理解：

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[i+1..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 和以下几道题都共享一些底层思维：

• 42. 接雨水：对每个位置取左侧最大值和右侧最大值的较小者，再减去当前高度，本质是“左右信息复用”。
• 152. 乘积最大子数组：要同时维护最大值和最小值，因为在处理负数时，一个很小的负数乘负数可能变成最大。这和 238 的“连着乘”直觉有直接关系。
• 560. 和为 K 的子数组：使用了前缀和思想，前缀和是“前缀积”的加法版本。
• 974. 和可被 K 整除的子数组：前缀和配合余数数组，用的也是同一个信息累计框架。

所以说，238 并不是一道孤立的题。它教给你的是“如何用一次遍历把某个方向上的累积信息存下来，再用第二次遍历去补上另一个方向”。这个思维在数组类题目里属于基础中的基础，值得多花时间吃透。

我个人刷题有个习惯：中等题至少写两种解法。第一遍按最直观的数组版本过，第二遍再优化空间。238 这种题特别适合这个练习方式，因为从 O(n) 空间优化到 O(1) 空间只改了半个循环，却能把“输出数组能不能算额外空间”“滚动变量怎么更新”这些细节全部串起来。最后再分享一个小技巧：刷这题的时候，别只盯着代码跑通，拿笔在纸上把ans数组每一轮的值写出来，写个两三组用例，你就再也不会忘记为什么right要最后更新了。