空间优化)
1. 题目理解与核心考点
1.1 题面拆解：这题到底在考什么
“238. 除了自身以外数组的乘积”这道题，我刷了不下三遍，每次面试前翻Hot 100还是会重新瞄一眼。原因很简单：它长得太像一道“暴力题”了，但真正动手写的时候，大多数人都会掉进“除法陷阱”里出不来。
题目原文不长：给你一个整数数组nums，返回一个数组answer，其中answer[i]等于nums中除了nums[i]之外其余各元素的乘积。题目还给了两个硬性约束：不能使用除法，时间复杂度要求 O(n)。
先别急着往下看，我建议你拿起笔，随便写一个数组试一下。比如nums = [1,2,3,4]，用手算的结果是[24,12,8,6]。24 是 2×3×4，12 是 1×3×4，8 是 1×2×4，6 是 1×2×3。手算很容易，可一旦约束你“不能用除法”，很多人的第一反应就卡壳了。
这题背后的核心考点，其实是前后缀分解（也常叫“左右乘积法”）。你不需要算全体乘积再除掉某个数，而是把“除了自身以外”拆成“左边的乘积 × 右边的乘积”。这个思维模型不仅这一题用得上，很多数组类、动态规划类的题目都能复用，所以我一直觉得它是Hot 100里性价比极高的一道题。
1.2 为什么“不能用除法”是这题的灵魂
有的读者可能会问：就算不能用除法，我先算出所有数的乘积total，然后answer[i] = total / nums[i]不就行了？如果题目没禁用除法，这确实是最快的方法，代码两行就写完。但面试官设置这个约束，背后有很实际的考量。
第一个理由是0 的问题。假设数组是[0, 1, 2, 3]，总乘积是 0，如果直接除以nums[i]，那么answer[0]就是0 / 0，根本没法算。你当然可以专门处理多个0的场景，但代码会一下子变得很啰嗦，而且容易漏边界。更别说数组里有两个0的情况 —— 只有0所在的位置结果非零，其余位置全是0，用除法实现你得单独开一遍逻辑判断。
第二个理由是溢出风险。虽然题目说数组元素在32位整数范围内，但“乘积”可不一定还在这个范围内。如果全部元素乘起来再逐一除，中间这个total很可能先溢出了。前后缀法只做局部乘法，每一步的乘积范围天然受约束，安全得多。
第三个理由更贴近面试本质：题目想筛选的是建模能力，不是计算能力。能想到“每个位置的结果 = 左边乘积 × 右边乘积”，说明你对数组扫描、状态累积这类基础技巧是理解的；而只会写除法的人，往往只是背过某个模板，换个约束就露馅。所以，把这题的“为什么不让用除法”想透，比多刷十道简单题都有价值。
2. 解法一：左右乘积数组（最直观的标准答案）
2.1 思路建模：把“除了自身”拆成两半
“除了自身以外”这个表述，乍一听是一个整体，但你可以换个角度看：对任意位置i来说，自身左边有一串数，右边有一串数，结果就是这两串数的乘积。左边那一串的乘积，可以提前算好存起来；右边那一串同理。最后每个位置只需要做一次乘法，把左和右拼起来。
具体来说，维护两个数组：
left[i]：nums[0]到nums[i-1]的乘积，也就是位置i左侧所有元素的乘积。注意left[0]没有左侧元素，按数学约定空乘积为 1。right[i]：nums[i+1]到nums[n-1]的乘积，也就是位置i右侧所有元素的乘积。同理right[n-1] = 1。
那么答案就是answer[i] = left[i] * right[i]。
这个思路有一点像把一列队伍从中间某个位置分成左右两段，左边的人数和右边的互不相干，先把两段的人数分别数清楚，再相乘。它不依赖任何除法，也天然规避了0的困扰，因为乘法中任何一个0都只是让结果归零，不会引发运行时错误。
2.2 代码实现：分步扫描，边界一目了然
以 Python 为例，最清晰的写法是分两次遍历，一次从左往右填left，一次从右往左填right，最后合成答案：
def productExceptSelf(nums): n = len(nums) left = [1] * n right = [1] * n answer = [1] * n # 从左往右，left[i] 存 nums[0..i-1] 的乘积 for i in range(1, n): left[i] = left[i - 1] * nums[i - 1] # 从右往左，right[i] 存 nums[i+1..n-1] 的乘积 for i in range(n - 2, -1, -1): right[i] = right[i + 1] * nums[i + 1] # 合并 for i in range(n): answer[i] = left[i] * right[i] return answer这里有几个容易写错的地方，我特别提醒一下：
- 遍历起点：填
left时，循环从1开始，因为left[0]已经是初始值 1，不需要再乘任何东西。填right时，循环从n-2开始，因为right[n-1]也是初始值 1。 - 下标对应：
left[i] = left[i-1] * nums[i-1]，不是nums[i]。如果你写成nums[i]，那就把当前位置自己也乘进去了，结果会错得离谱。 - 空数组：如果
n = 0，三个数组都是空列表，返回空即可，代码自然兼容。如果面试官问“单元素数组[5]”，答案应该是[1]，因为“除了自己以外没有任何元素”，空乘积约定为 1，这种约定在数学和工程里都很常见。
你可以把以上逻辑翻译成 C++ 或 Java，结构一模一样：
vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> left(n, 1), right(n, 1), answer(n, 1); for (int i = 1; i < n; ++i) { left[i] = left[i - 1] * nums[i - 1]; } for (int i = n - 2; i >= 0; --i) { right[i] = right[i + 1] * nums[i + 1]; } for (int i = 0; i < n; ++i) { answer[i] = left[i] * right[i]; } return answer; }这个版本的时间和空间复杂度都是 O(n)，代码逻辑非常直白，适合作为面试时的“保底答案”。如果你只想让考官看到你可复现、稳扎稳打的功底，完全可以就停在这里。但如果想多拿一点印象分，往下看优化版。
3. 解法二：空间优化到 O(1) —— 面试加分的关键一步
3.1 优化动机：left 和 right 能不能只留一个
上面的解法和“暴力算总乘积再除法”相比，已经算是标准答案了，但考官通常还会追问一句：“能不能把额外空间降到 O(1)？”注意这里的 O(1) 指的是除了返回数组本身之外不用额外数组。换句话说，answer是必须返回的，不能算在额外空间里；但left和right这两个辅助数组是可以省掉的。
怎么省？我再观察一下计算过程：answer[i] = left[i] * right[i]。如果我先用answer把left的结果存下来，然后从右往左扫一遍，同时用一个变量right动态累积右侧乘积，那么每个位置都可以当场算出答案。这样唯一保留下来的“数组”只有answer本身，额外空间就是常数级。
这其实是一种很常见的优化技巧：第一个循环把中间结果暂存在输出数组里，第二个循环用滚动变量覆盖。理解了这个套路，以后再遇到“原地修改数组原地求值”的题，你会敏锐很多。
3.2 代码实现：两遍遍历，一个变量搞定
直接看代码：
def productExceptSelf(nums): n = len(nums) answer = [1] * n # 第一遍：从左往右，answer[i] 暂时存左侧乘积 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我把这段代码的每一步手动推演一遍，方便你看清它为什么是对的。假设nums = [1, 2, 3, 4]：
- 第一遍结束后，
answer = [1, 1, 2, 6]。这四个数分别代表每个位置的左侧乘积：位置0左侧没有元素，是1；位置1左侧是1；位置2左侧是1×2=2；位置3左侧是1×2×3=6。 - 第二遍开始时
right = 1。处理i = 3，answer[3] = 6 * 1 = 6，然后right = 1 * 4 = 4；处理i = 2，answer[2] = 2 * 4 = 8，然后right = 4 * 3 = 12；处理i = 1，answer[1] = 1 * 12 = 12，然后right = 12 * 2 = 24；处理i = 0，answer[0] = 1 * 24 = 24。
最后得到[24, 12, 8, 6]，完全正确。整个过程只有right这一个额外变量在不断滚动，空间占用不随数组规模变化。
C++ 版本同样简洁：
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; }很多第一次看这个解法的读者会困惑：为什么要先乘right再更新right？顺序能不能反过来？这里的关键是：处理answer[i]时，right必须表示“i 右侧所有元素的乘积”，也就是nums[i+1..n-1]的乘积。如果先更新再乘，right就会把nums[i]自己也乘进去，结果就错了。这个细节我面试时亲耳听过有人答反，当场就能看出对方对状态变量的理解是否扎实。
3.3 为什么“输出数组不算额外空间”是合理约定
有些同学会举手提问：answer明明也是个 O(n) 的数组，凭什么说空间复杂度是 O(1)？这其实是算法题里一条约定俗成的规则：函数必须返回一个结果数组，这个数组占的空间不参与额外空间统计。就像你写排序算法，如果允许原地排序，交换变量占了 O(1)，但数组本身就是输入参数，自然不能算额外开销。
在实际工程里，这种约定也说得通：内存申请者本来就要为返回值分配空间，能否省掉的是“临时辅助”这块开销。面试时如果你想表达得更严谨，可以主动说一句“不算输出数组的话，额外空间是 O(1)”，大多数考官立刻就会给你加分。
4. 复杂度对比与面试答题节奏
4.1 一表看懂三种思路的取舍
面试过程中，很多时候你不需要立刻写出最优解，但你需要在到达最优解之前，清楚地说明每一层优化的理由。强行背一个答案并不难，难的是让面试官觉得你“想明白了”。我整理了一张表，方便对照：
| 解法 | 时间复杂度 | 额外空间 | 是否满足“不用除法” | 适用场景 | 推荐指数 |
|---|---|---|---|---|---|
| 先求总乘积再逐个相除 | O(n) | O(1) | 否（违反约束） | 仅当题目允许除法且无0时 | 不推荐 |
| 左右乘积数组 | O(n) | O(n) | 是 | 思路最直观，适合初学时理解 | 推荐 |
| 输出数组复用 + 滚动变量 | O(n) | O(1) | 是 | 面试首选，空间敏感场景 | 强烈推荐 |
横向对比后你会发现，除法方案因为踩了题意红线，几乎可以无视；左右数组方案是教学意义上的“标准答案”；而复用输出数组的方案，才是实战面试中最值得写的版本。它没有牺牲可读性，又把空间降到了最优，是性价比最高的一条路。
4.2 面试话术：从读题到写出最优解的完整示范
我当年在模拟面试里练过这道题很多次，后来也帮别人mock过多次，总结出一套比较好用的表达节奏，分享给你：
第一步，先复述题意并确认约束。我会说：“输入是整数数组，要求返回每个位置除自身以外元素的乘积，不能用除法，O(n) 时间内。”这一步能让面试官确认你没跑偏。
第二步，说朴素想法，但主动否定：“最直接的做法是求出总乘积再除以每个元素，但一是题目禁止除法，二是数组里有0时会出问题，所以得另想办法。”
第三步，切换到前后缀思路：“每个位置的结果可以看作‘左侧乘积 × 右侧乘积’。我先把每个位置的左侧乘积算出来，再从右往左把右侧乘积乘上去。”这里可以顺手画个数组下标示意图，面试时边画边说，比自己闷头写代码效果好得多。
第四步，写代码，同时轻声讲关键点。写到第二遍循环时，顺口提一下right变量“先乘后更新”的原因。写完之后，立刻用[1,2,3,4]手动验证一遍，再补测[0,1,2]或单元素数组。
第五步，主动总结复杂度：“时间复杂度 O(n)，三次循环或两次循环都是线性；额外空间 O(1)，因为复用了输出数组。”
这一整套流程大约3到5分钟，比直接贴出最优解更能体现你的思考过程。面试官要的不是一个能背答案的人，而是一个遇到陌生问题也能拆解出思路的人。
4.3 现场推演的边界用例
手算demo时，我建议至少准备三个用例：
- 常规场景：
nums = [1,2,3,4]，预期[24,12,8,6]。这是你写代码后第一遍自测的用例。 - 含零场景：
nums = [0,1,2]，预期[2,0,0]。用前后缀法完全不需要特判，直接套公式就得到正确答案，顺便展示“不依赖除法”的优势。 - 单元素场景：
nums = [5]，预期[1]。很多人会在这里犯迷糊，其实空乘积约定为1，answer[0]初始化就是 1，两遍循环都不进入或只进入一次，结果自然正确。
除了这三个用例，还可以看一眼nums = [1, -1]，预期[-1, 1]，验证负数乘积没问题。边界用例不是走过场，它能帮你既说服面试官，也防止自己写着写着下标越界。
5. 常见问题与边界条件速查
5.1 高频出错点和排查思路
虽然这道题代码很短，但我见过太多人栽在一些不起眼的小地方。下面这几个问题，是我在平时帮别人review代码时最常遇见的：
第一个是循环边界写错。填left时用了range(n)，结果把nums[i]自己也乘了进去；或者从右往左时写成range(n, -1, -1)，越界访问answer[n]。这类问题靠语法检查很难发现，因为数组初始化为1时，多乘一个1不会让结果立刻报错，只有数据不凑巧时才露馅。所以我每次写这种前后缀循环，都会先在纸上确认一遍：第一个循环从1开始，第二个循环从n-2开始，或者用range(n-1, -1, -1)配合变量滚动。
第二个是对“0”的处理时机。如果面试官追问“数组里有0怎么办”，有些同学会下意识地想在代码里加if nums[i] == 0之类的分支。其实前后缀法根本不需要这个分支，0 会自动让对应位置的乘积归零。你只需要自信地解释一遍原理，而不是慌慌张张地补补丁。
第三个是整数溢出。题目通常在 32 位整数范围内给出答案，但如果你在本地测试时用了更大的数，可能会溢出。LeetCode 的测试用例一般不会让你溢出，但在 C++ 里写乘法时养成用long long的习惯，或者心里清楚哪些位置可能结果特别大，总归不是坏事。
5.2 一题多语言实现的细节差异
这道题在主流语言里写起来大同小异，但有几个细节需要注意。
Python 版本最简洁，风险在于answer = [1] * n这种初始化是否满足你的需求（这里是创建独立列表，不用担心引用共享问题）。Java 版本要注意int[] answer = new int[n]; Arrays.fill(answer, 1);，因为 Java 默认数组元素是 0，不填 1 会让乘法结果全变 0。C++ 版本和Java类似，vector<int> answer(n, 1)一行搞定，没有默认值陷阱。
还有个跨语言的通病：有人在第二遍循环时用了两个变量，一个right一个left，其实完全没必要。左乘积已经存在answer里了，右乘积用滚动变量即可。少一个变量，代码更简洁，也更容易解释。
5.3 区域误区：面试中千万不要说的“讨巧方案”
最后说一个我提醒过很多学生的点：不要拿“允许使用额外API”去钻空子。有些语言提供现成的累积乘法库函数，或者有人会提议“用对数把乘法变加法，再用指数还原”。这两种思路都不太合适。
为什么？因为题目明确要求不能用除法，本质是在考察你对乘法结构本身的理解。用对数技巧的话，浮点数误差会让你在某些测试用例上直接挂掉，而且面试官一看就知道你在取巧，对你的印象分会大打折扣。老老实实写前后缀优化版，比什么花活都强。
如果真的想多聊一个话题，可以是“如果数组里只有一个0，用除法方案怎么处理”。这个延展能显示出你对边界情况的掌控力，但别把它当作主方案。
6. 复盘与扩展思考
6.1 这道题的“母题意义”：前后缀技巧的迁移
每道 Hot 100 的题目我都习惯做一次“认知提炼”，问自己：这道题除了背答案，真正教会了我什么？对于 238 题，答案是前后缀分解思想。
这个概念你在很多地方都见过：前缀和、后缀和、前缀最大、后缀最小……本质上都是“把对全体的查询，拆成对左右两侧的预处理”。举个例子，你下次遇到“求每个位置左侧比它大的元素个数”这类题，第一反应就可以是“能不能用某种方式先预处理左侧信息，再在线计算”？一旦建立了这种思维，很多题目的第一层朴素解法就不再是暴力遍历了。
再举个例子：有一类“除自身之外的最值”题目，比如“返回每个元素之外的最大值”，思路一模一样，无非是把乘积换成最大值运算。可见这个套路不是死记硬背，而是可以举一反三的。
6.2 如果允许除法但存在多个0，你会怎么处理
作为面试后的延伸讨论，你可以主动向面试官抛出这个问题。思路是这样的：
- 统计数组里 0 的个数。
- 如果 0 的个数为 0，直接用总乘积除以每个元素。
- 如果 0 的个数为 1，只有那个0所在的位置结果是“其余所有非零元素的乘积”，其他位置全是 0。
- 如果 0 的个数大于等于 2，所有位置结果都是 0。
这个方案虽然满足“能用除法”的假设，但代码分支比前后缀法多不少。把这个对比想明白，你就不难理解：前后缀法的优势不只是绕开除法约束，而是天然规避了因0引发的多种特殊情况。这也是为什么它在工程意义上更稳健。
6.3 一道题牵出的复习路线
如果你刚刷到这道题，我觉得可以顺便把下面这类题目一起过一遍：
- 前缀和系列：求区间和、求子数组满足某条件的数量。这类题考验的是“预处理查询”，和238的思路最接近。
- 原地修改数组系列：像“除自身以外数组的乘积”这种“输出数组复用输入数组”的技巧，在字符串轮转、数组压缩等题目里也会出现。
- 前后缀极值系列：比如每个位置的“左边最大值和右边最小值”，常用于分治算法里的预处理环节。
把这些题目按“思维模型”归类，比按题号顺序刷要高效得多。每次碰到新题，先问自己：它的解法本质是“前缀思想”还是“滑动窗口”，还是“二分查找”？答上来，你的刷题就开始有体系了。
7. 写在最后的实操心得
这道题我刷了三遍，每一遍都有新体会。第一遍只学会了左右数组写法，觉得还挺“绕”；第二遍理解了滚动变量优化，开始惊叹于这种“一个数组顶两个用”的优雅；第三遍是在帮别人做模拟面试时，才真正把“为什么不能用除法”“为什么0不是问题”“为什么输出数组不算空间”这些问题都串了起来。所以我强烈建议你，不要只满足于提交通过，一定要做一次“口头讲解”——找一个朋友，或者在白板上对着空气讲一遍思路。如果能在不看代码的情况下把逻辑流畅地讲出来，说明你是真的理解了。
最后再分享一个小技巧：刷题时准备一个“边界用例清单”，每道题至少三个边界用例。对这道题，我的清单是[1,2,3,4]、[0,1]、[5]。这三个用例加起来刚好覆盖了常规、零值和单元素三种情况。等你在键盘上敲代码前先过一遍这几个输入，大概率就不会出现低级错误。这题可以就此打住，但前后缀的技巧，建议你继续在其他数组题里多用几次，用熟练了，它会成为你算法工具箱里一把非常顺手的家伙。
