优化)
刷 LeetCode 的人应该都有这种感觉：有些题第一眼看过去，觉得"这不就是求个乘积吗"，然后动手一写才发现处处是坑。
"除自身以外数组的乘积"（LeetCode 238，Product 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和right：
left[i]表示nums[0]到nums[i-1]的乘积，也就是 i 左侧所有元素的乘积。right[i]表示nums[i+1]到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 = 1：
i = 3：answer[3] = 6 * 1 = 6，然后right = 1 * 4 = 4i = 2：answer[2] = 2 * 4 = 8，然后right = 4 * 3 = 12i = 1：answer[1] = 1 * 12 = 12，然后right = 12 * 2 = 24i = 0：answer[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，右侧乘积是 6，0 乘 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]：
- 总乘积 = 0
answer[0] = 0 / 0，无法计算
如果数组是[1, 0, 2]：
- 总乘积 = 0
answer[1] = 0 / 0，还是无法计算
如果数组是[0, 0, 2]：
- 总乘积 = 0
answer[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/C++：size_t 与指针数组的经典坑
C++ 版本直接拿vector<int>写：
class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> 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)就会死循环，因为无符号数永远大于等于 0，i 减到 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 会发生什么"。这些追问，才是这道题真正要考察的东西。
