企业官网建设流程全解析

这道题是 LeetCode 上的经典题《除自身以外数组的乘积》，题号 238，也长期挂在 LeetCode 热门 100 题里。题目表面平平无奇：给定一个数组，让你返回一个新数组，每个位置存放的是“原数组中除了这个位置以外所有元素的乘积”。听起来像是练手题，但它的限制条件“不能使用除法”直接卡掉了一大半人的第一反应。我刷了不少题，周赛 430 打完之后再回头看这道题，越发觉得这类经典题才是很多新题的底子——它不考什么冷门技巧，考的是你有没有把一个看似简单的结构真正想清楚。

我第一次见到这题的时候，第一反应是“总乘积除以当前数不就行了”，然后被“不能用除法”四个字噎住。后来翻了题解，再自己推导，才发现这道题的精华根本不在计算，而在“乘积结构”的拆法上。我后来把这道题反复刷了三遍，每一遍都能看到新的东西：先是暴力，再是前缀积/后缀积，最后才体会到常数空间的右乘变量是怎么回事。这篇文章就把我整个思考过程和踩过的坑完整写出来，希望能帮到正在刷题的读者。

1. 为什么说这道题经典：一道被“禁掉除法”逼出来的思维题

1.1 题目原文、数据范围与第一反应

先把题目说清楚：给定整数数组nums，长度为n，要求返回一个同样长度的数组answer，其中answer[i]等于nums中除nums[i]之外其余所有元素的乘积。

题目还给了几个硬性约束：

• 不能使用除法；
• 时间复杂度要达到 O(n)；
• 题目保证任意前缀乘积、后缀乘积都落在 32 位整数范围内。

很多人看到这道题的第一反应都是这样：

total = 1 for num in nums: total *= num return [total // num for num in nums]

用 Python 写出来甚至很简洁。然后你突然发现不让用除法，第二反应是“那我用数学技巧搞一下，比如乘上倒数？”整型数组里做倒数根本不可行。于是思路卡在这里。

这里其实就是这道题第一个精妙的地方：它考察的不是你会不会某个算法，而是你能不能在两三个“最直观但走不通”的路线面前，退回来重新审视问题结构。

我后来在面试模拟中看到很多候选人栽在这一步：他们把标准解法背得很熟，但当我追问“为什么不能用除法”时，却只能说出“题目不让用”。这其实是不够的。

1.2 为什么出题人会刻意禁止除法

我最初觉得“禁止除法”是出题人故意刁难，后来仔细想了想，发现这个限制背后至少有三个实际理由，每一个都指向真实的工程场景。

第一个理由：除以零的边界情况非常麻烦。假设nums中有一个 0，总乘积是 0，那么0 / 0在数学上就不成立。假设有两个 0，其他位置也都不是正常乘法能直接算出来的。允许除法意味着每个位置都要特判 0 的个数，逻辑会变得乱七八糟。题目希望考察的是稳扎稳打的“乘法累乘”，而不是靠除法和一堆 if 去绕。

第二个理由：整数除法不是安全的。题目保证乘积在 32 位整数范围内，但如果先算总乘积再除以某一个数，中间那个总乘积可能已经很大了，如果total是 32 位带符号整数，一旦溢出就可能出现负数或回绕，后果很难排查。Python 里的整数可以无限大，所以不太能体会到这一点，但在 C++、Java 里这是真实的溢出隐患。

第三个理由是更核心的：这道题想让你构造一个结构，而不是找一个逆运算。前缀积和后缀积这种“从左侧累积、从右侧累积”的思想，可以平移到区间查询、二维矩阵、动态规划等场景里。除法本质上是一个捷径，也是一个“作弊工具”，它绕开了题目真正想让你掌握的累乘思维。

我自己的体会是：拿到这类题，先别急着骂限制条件，想想这个限制在逼你放弃什么、想在让你学会什么。想清楚这一点，解法自己就浮现出来了。

2. 暴力解与乘积结构拆解：先看清答案到底长什么样

2.1 暴力双循环慢在哪里

在讨论最优解之前，先把最直观的暴力解法写出来。这样可以看清问题的复杂度瓶颈到底在哪里。

def product_except_self_brute(nums): n = len(nums) res = [] for i in range(n): prod = 1 for j in range(n): if i == j: continue prod *= nums[j] res.append(prod) return res

这是最容易想到的写法：两层循环，第一层确定“要跳过哪个位置”，第二层把所有其他数字乘起来。逻辑没有错，但复杂度是 O(n²)。当n是 100 时还无所谓，当n是 10⁵ 时，相乘操作会达到 10¹⁰ 量级，任何在线评测系统都不可能让这个代码通过。

这里最值得注意的事情是：暴力解告诉我们答案的形态——answer[i]就是“所有元素的乘积中，去掉第 i 个元素”的结果。如果你把它看作“整体减去一个元素”，你就只会想到除法；如果你把它看作“左边一段的乘积，乘上右边一段的乘积”，你就找到了正解。

2.2 最关键的观察：左边乘积乘右边乘积

我们拿一个具体数组来拆：

nums = [1, 2, 3, 4]

手动计算一下期望结果：

answer[0] = 2 * 3 * 4 = 24 answer[1] = 1 * 3 * 4 = 12 answer[2] = 1 * 2 * 4 = 8 answer[3] = 1 * 2 * 3 = 6

看第二个位置i = 2，对应的answer[2] = 1 * 2 * 4。如果把1 * 2和4分开来看，它们恰好是nums[2]左边所有元素的乘积，和右边所有元素的乘积。也就是说：

answer[i] = nums[0] 到 nums[i-1] 的乘积 × nums[i+1] 到 nums[n-1] 的乘积

这个观察很关键：每个位置的结果都可以从“左侧乘积”和“右侧乘积”两部分拼出来。左侧信息可以从左往右扫一遍得到，右侧信息可以从右往左扫一遍得到。两个方向各扫一次，正好能覆盖所有位置。

我第一次想到这个结构时，感觉有点像是“给每个位置开两份抽屉”：左边抽屉里放的是从 0 号位置一路乘到 i-1 的累积积，右边抽屉里放的是从末尾一路倒乘到 i+1 的累积积。两个抽屉一合并，就是答案。这个比喻虽然朴素，但真的帮我避免了代码里下标搞混的问题。

3. 前缀积加后缀积：O(n) 空间的直观写法

3.1 前缀积表：从左往右递推

既然已经意识到需要“左侧乘积”和“右侧乘积”，最直接的做法就是预先把两张表算出来。

先看前缀积表prefix，我把它定义为：

prefix[i] = nums[0] * nums[1] * ... * nums[i-1]

也就是nums[i]左边所有元素的乘积。注意这里下标是左开右闭的：prefix[0]表示“0 左边所有数的乘积”，也就是一个元素都没有，乘积定为 1。

递推公式很自然：

prefix[0] = 1 prefix[i] = prefix[i-1] * nums[i-1]

写成 Python 代码：

def build_prefix(nums): n = len(nums) prefix = [1] * n for i in range(1, n): prefix[i] = prefix[i - 1] * nums[i - 1] return prefix

拿nums = [1, 2, 3, 4]来模拟一遍：

prefix[0] = 1 prefix[1] = prefix[0] * nums[0] = 1 * 1 = 1 prefix[2] = prefix[1] * nums[1] = 1 * 2 = 2 prefix[3] = prefix[2] * nums[2] = 2 * 3 = 6

最后得到：

prefix = [1, 1, 2, 6]

很多人在这里会犯一个错误，就是写成prefix[i] = prefix[i-1] * nums[i]。那样的话，prefix[2]就变成了1 * 2，而实际它应该是1 * 1 * 2，也就是2。虽然例子碰巧对得上，但在更长的数组里这个偏差会一直传导到后面，整张表都会错。写这道题时，一定要先想清楚“第 i 个位置代表的到底是左边多少个元素的乘积”。

3.2 后缀积表：从右往左递推

右侧乘积表suffix我用对称的方式定义：

suffix[i] = nums[i+1] * nums[i+2] * ... * nums[n-1]

也就是nums[i]右边所有元素的乘积。针对边界情况：

suffix[n-1] = 1

因为最后一个位置右边没有任何元素。递推从右往左：

suffix[i] = suffix[i+1] * nums[i+1]

写成代码：

def build_suffix(nums): n = len(nums) suffix = [1] * n suffix[n - 1] = 1 for i in range(n - 2, -1, -1): suffix[i] = suffix[i + 1] * nums[i + 1] return suffix

继续用nums = [1, 2, 3, 4]模拟：

suffix[3] = 1 suffix[2] = suffix[3] * nums[3] = 1 * 4 = 4 suffix[1] = suffix[2] * nums[2] = 4 * 3 = 12 suffix[0] = suffix[1] * nums[1] = 12 * 2 = 24

得到：

suffix = [24, 12, 4, 1]

这里我要特别强调一下循环边界：range(n - 2, -1, -1)表示从n-2开始，一直取到0，每步减一。如果写成range(n - 1, -1, -1)，就会在i = n-1时执行suffix[n-1] = suffix[n] * nums[n]，触发越界。这个边界是新手最容易翻车的地方之一。

3.3 合并两张表得到答案

现在，answer[i] = prefix[i] * suffix[i]就是最终结果。完整代码如下：

def product_except_self(nums): n = len(nums) prefix = [1] * n for i in range(1, n): prefix[i] = prefix[i - 1] * nums[i - 1] suffix = [1] * n for i in range(n - 2, -1, -1): suffix[i] = suffix[i + 1] * nums[i + 1] ans = [] for i in range(n): ans.append(prefix[i] * suffix[i]) return ans

依然用[1, 2, 3, 4]验证，三张表放一起看：

结果正确。这个版本的时间复杂度是 O(n)，空间复杂度是 O(n)，因为额外用了两张长度都为 n 的表。

这个写法的优点是逻辑非常清晰、不容易出错，是我推荐给初学者的第一版。但它显然还不是最优的，因为题目里描述的“额外空间 O(1)”版本，才是面试官真正想看的。

4. 常数空间优化：用一个变量省掉整个后缀数组

4.1 核心观察：后缀表是“流式使用”的

在空间复杂度上做文章，首先要意识到一个问题：在计算最终答案时，我们是先从头到尾把prefix算完，再从尾到头把suffix的信息合并进去。也就是说，right side 的信息根本不需要一次性全部存下来，可以在从右往左遍历的过程中用一个变量动态维护。

这个变量叫R。遍历到位置i的时候，R恰好等于nums[i+1]到nums[n-1]的乘积。算完answer[i]之后，再把R乘以nums[i]，这样当i往前移动到i-1时，R就已经是nums[i]到nums[n-1]的乘积了，而这正是计算answer[i-1]所需要的右侧乘积。

这里有一个顺序上的坑：在位置i，必须先拿当前的R去乘answer[i]，然后再更新R = R * nums[i]。如果顺序反了，R就会混入nums[i]本不该乘进去的那个数，导致整个数组全部算错。

4.2 手把手模拟一遍

以nums = [1, 2, 3, 4]为例，我完整写一遍演进过程。

初始化：

ans = [1, 1, 1, 1]

第一遍正向遍历，用ans本身保存前缀积：

i = 1: ans[1] = ans[0] * nums[0] = 1 * 1 = 1 i = 2: ans[2] = ans[1] * nums[1] = 1 * 2 = 2 i = 3: ans[3] = ans[2] * nums[2] = 2 * 3 = 6

此时：

ans = [1, 1, 2, 6]

这个数组里存的就是每个位置左边所有元素的乘积。

然后从右往左遍历，同时维护R：

R = 1 i = 3: ans[3] = ans[3] * R = 6 * 1 = 6 R = R * nums[3] = 1 * 4 = 4 i = 2: ans[2] = ans[2] * R = 2 * 4 = 8 R = R * nums[2] = 4 * 3 = 12 i = 1: ans[1] = ans[1] * R = 1 * 12 = 12 R = R * nums[1] = 12 * 2 = 24 i = 0: ans[0] = ans[0] * R = 1 * 24 = 24 R = R * nums[0] = 24 * 1 = 24

最终：

ans = [24, 12, 8, 6]

模拟结果正确。注意最后一次R的更新虽然不再影响任何答案，但程序里继续执行没有任何问题，因为循环已经结束了。

4.3 完整代码与“O(1) 额外空间”的解释

常数空间版本的完整 Python 代码：

def product_except_self(nums): n = len(nums) ans = [1] * n # 从左到右：ans[i] = 左边所有元素的乘积 for i in range(1, n): ans[i] = ans[i - 1] * nums[i - 1] # 从右到左：用 R 保存右边所有元素的乘积 R = 1 for i in range(n - 1, -1, -1): ans[i] = ans[i] * R R = R * nums[i] return ans

时间复杂度仍然是 O(n)——准确说执行了两次循环，加起来是 2n 次乘法，但常数倍不影响复杂度等级。空间复杂度方面，除了必须返回的ans数组之外，只额外使用了一个变量R，所以额外空间是 O(1)。如果面试官把输出数组也计入空间，那就是 O(n)，但通常讨论算法空间复杂度时，默认不算返回值本身。这一点建议在面试时主动提一句，能体现出你确实理解空间复杂度的含义。

4.4 为什么必须两次遍历，不能一次搞定

有人可能会问：能不能只走一遍就把结果算出来？答案是：不行。原因是每个位置需要同时知道“左侧累积信息”和“右侧累积信息”。数组是单向的，从左往右扫只能拿到左侧信息，从右往左扫才能拿到右侧信息。想要覆盖所有位置，两趟扫描是信息最少的下界。这也是为什么这道题的解法看起来“不过两遍循环”，但依然是 O(n) 里比较优雅的答案。

另外，第一遍正向循环从i = 1开始，而不是i = 0，因为ans[0]左侧没有元素，所以初始化为 1 就对了。第二遍逆向循环从i = n-1开始，此时R = 1，代表最后一个位置右边没有元素。这两个初始化的“1”不是拍脑袋写的，它们对应乘法单位元，是整个递推链能正确启动的基础。

5. 易错场景、面试追问与同类题对比

5.1 边界用例：长度为 2、单个 0、多个 0

我先说一个很多人忽略的点：这道题的数据范围通常要求n >= 2，所以不需要为长度为 0 的数组做特殊处理。但长度为 2 的情况是最容易出错的边界，因为左右两侧都非常短。

拿nums = [3, 4]来测一下常数空间代码：

正向： ans[1] = ans[0] * nums[0] = 1 * 3 = 3 ans = [1, 3] 逆向： R = 1 i = 1: ans[1] = 3 * 1 = 3, R = 4 i = 0: ans[0] = 1 * 4 = 4 ans = [4, 3]

结果是[4, 3]，正确。

再看包含一个 0 的情况，比如nums = [1, 0, 3, 4]：

正向： ans = [1, 1, 0, 0] 逆向： R = 1 i = 3: ans[3] = 0 * 1 = 0, R = 4 i = 2: ans[2] = 0 * 4 = 0, R = 12 i = 1: ans[1] = 1 * 12 = 12, R = 0 i = 0: ans[0] = 1 * 0 = 0 ans = [0, 12, 0, 0]

第 1 个位置（下标 1）的结果是12，也就是1 * 3 * 4，其他位置只要乘到了 0，结果都是 0。逻辑正确。

如果数组里有多个 0，比如nums = [1, 0, 3, 0]，结果是[0, 0, 0, 0]，因为任何非 0 位置都乘到了某个 0。代码跑出来也是全 0，这个不用特判。

那如果允许除法，0 怎么处理？需要先统计 0 的个数。如果 0 多于 1 个，答案全 0；如果恰好 1 个 0，那个 0 位置的结果是非 0 元素的乘积，其他位置全是 0；如果没有 0，就正常做“总积除以当前元素”。你会发现这套 if-else 逻辑非常啰嗦，而且边界一多就容易漏。所以题目直接用“禁止除法”把这个复杂度从源头砍掉了。

5.2 写代码时最容易翻车的三个点

第一个是下标错位。前缀积那一步，ans[i] = ans[i - 1] * nums[i - 1]，很多人会写成nums[i]。表面看数组范围没越界，但语义完全错了：ans[i]代表 “i 左边所有数的乘积”，而nums[i]自己是在i位置上的数，按定义不应该乘进去。

第二个是第二遍循环的边界。range(n - 1, -1, -1)中间那个-1表示终止位置，很多人会写成range(n - 2, -1, -1)，导致最后一个位置没被更新。这个问题在短数组上特别隐蔽，比如长度 2 时，i从0开始（因为n-2 = 0），ans[1]从来没有被R处理过，但示例结果还是碰巧对的，就更容易漏掉。

第三个是R的更新时机。我再强调一遍：先用R更新ans[i]，再执行R *= nums[i]。如果反了，R就会多乘一个当前数，而当前数本来应该被排除在外。我见过不少背了代码但没理解这一步的人，面试时被追问一句“为什么顺序不能交换”就直接愣住了。所以我会建议你把第 4.2 小节的模拟亲手画一遍，把R在每个位置的值写下来，体会一次“提前更新”会让结果偏移多远。

5.3 面试官常问的变体与扩展题

这道题本身很短，但面试官很喜欢在它基础上做扩展。最常见的变体是：如果不要求“在 O(n) 时间内一次给出所有答案”，而是允许你先做预处理、再多次查询，你会怎么做？

答案是利用前缀积和后缀积两张表。预处理prefix和suffix都是 O(n)，之后每次查询answer[k]，只需要返回prefix[k] * suffix[k]，单次查询 O(1)。这种“预处理加 O(1) 查询”的模式在很多高频面试题里都会出现。

第二个变体是把一维数组推广到二维矩阵：要求计算矩阵中每个位置“除自身所在行和列之外所有元素的乘积”。思路本质相同，只是把左侧乘积拆成“行乘积”和“列乘积”，需要分别从行、列两个方向做累乘。看到变体时，先回到“拆结构”的思路，而不是背答案，就能迁移过来。

第三个变体是如果要把所有结果对一个大质数取模，比如对1_000_000_007取模。因为乘法和取模运算可以交换顺序，你可以先对数组里的每个数取模，然后每一步乘完立刻取模。注意一点：如果使用除法方案，碰到模运算里的除法就需要求逆元，复杂度直接就上去了。这又是一个“禁止除法”反而让你绕开麻烦的例子。

第四个常见的追问是“为什么前缀积数组里要存i左边的乘积，而不是包含i的乘积？”这个问题背后其实是定义的选择。如果把prefix[i]定义为包含nums[i]的累积积，那么在计算最终答案时就得错开一个下标，容易混乱。定义成“左边乘积”能直接对应到answer[i]，代码也更不容易出错。面试时能把定义讲清楚，会比硬背公式加分很多。

5.4 和“爱吃香蕉的狒狒”这类题的横向对比：刷题到底在练什么

我在刷 LeetCode 热门 100 题的时候，经常把《除自身以外数组的乘积》和 073《爱吃香蕉的狒狒》放在一起去想。表面上看这两题八竿子打不着：一个考数组累乘，一个考二分查找。但它们有一个共同点：第一直觉都很好用，但第一直觉又会撞上复杂度墙。

爱吃香蕉的狒狒那题，朴素做法是模拟每一小时吃多少根，然后从小到大试速度，最坏情况会非常慢。正解是意识到“速度”和“吃完所需时间”之间存在单调关系，于是用二分查找把试错过程从线性变成对数级。而本题是第一直觉“总积除以当前数”被题目规则直接禁掉，正解是意识到乘积可以按位置拆成左右两段，每一段都只用一趟遍历就能算完。这两道题背后都是同一个训练目标：拿到题目后，不要满足于“能跑”，而是去问“慢在哪、瓶颈是什么、能不能换一种结构表达”。

很多人刷题喜欢背模板，但一旦遇到变形就懵。我觉得真正值得刷的经典题，恰恰是这类结构感很强的题：解法不长，但每一步都有“为什么”。把这题吃透，再去碰周赛里那些前缀、区间、二维矩阵的题目，会轻松很多。这也解释了为什么它在 LeetCode 热门 100 题里地位那么稳——一道十行代码就能讲明白的题，却能把数组扫描、复杂度分析和边界处理都串起来。

我自己带过的一些学员在复述这道题时，常常能说出代码逻辑，但讲不出“为什么第二遍要逆序”“为什么 R 更新要在乘法之后”。我的建议是：不要急着往下刷，先把这道题当成一个小课题，把暴力解、前缀后缀解、常数空间解三个版本都亲手写一遍，再把示例数组的每一步推演写在纸上。这个过程花不了半小时，但会让你的理解牢固很多。尤其到面试现场，能条理清晰地讲出“我为什么这样设计遍历顺序”，远比默写正确代码更能打动面试官。