企业官网建设流程全解析

刷到 LeetCode 热题 100 里的“除自身以外数组的乘积”时，我第一反应是：这题有什么难的，算出全体乘积再逐个除掉不就行了？仔细一看，题目明确要求不要使用除法，还希望额外空间做到 O(1)——这一下就把大多数人最顺手的暴力思维堵死了。本文用 Java 把这个题从暴力解法一路拆到空间优化的最优实现，把每一步的思路、代码和真正坑过我的细节都写清楚。无论你是刚准备面试的应届生，还是想补算法短板的在职开发，这题都是一个非常好的“渐进优化”训练样本。

1. 这道题到底在考什么：为什么“除法”被明令禁止

1.1 题目定义与两个关键示例

先把题目说清楚。给定一个整数数组nums，请返回一个同样长度的数组answer，其中answer[i]是原数组中除nums[i]之外所有元素的乘积。题目给出的限制里有两条最扎眼：不使用除法，且在使用 O(1) 额外空间的条件下完成（输出数组不计入额外空间）。

示例：

输入: [1,2,3,4] 输出: [24,12,8,6] 输入: [-1,1,0,-3,3] 输出: [0,0,9,0,0]

第一个例子很常规，第二个例子专门放了一个 0。别小看这个 0，它直接影响你能否用除法偷懒。

1.2 “总乘积除以自身”方案的致命伤

很多人的第一直觉是：先算total = nums[0] * ... * nums[n-1]，然后answer[i] = total / nums[i]。这段逻辑在没有 0 的数组上完全正确，还能做到 O(n) 时间、O(1) 空间，看起来比任何优化都要强。但只要数组里出现一个 0，这条路就断了：total是 0，遇到nums[i] == 0时直接除零异常；就算用特判躲过去，你也必须反复统计 0 的个数才能确定哪些答案是 0、哪个答案是“除 0 外所有元素的乘积”。这道题把除法禁掉，本质上是逼你去想比“总体乘积倒推”更本质的做法。

1.3 真正要掌握的核心洞察：左右拆分

再看answer[i]的构成。对于[a, b, c, d]，answer[2] = a × b × d。把数组以当前位置为界劈成两半，a × b是左边部分的乘积，d是右边部分的乘积——answer[i]永远等于“左侧所有元素的乘积 × 右侧所有元素的乘积”。题目立刻从“求全局乘积再剔除自己”变成了“分别预计算每个位置左侧和右侧的累积乘积，再相乘”。这就是解这道题的地基，也是它想考察的思维模型：当每个输出都依赖“除自身之外的整体信息”时，不要老想着从整体中剔除自己，而是把整体拆成两个可预计算的半边，最后拼起来。

2. 暴力解法不是废柴：先把能跑对的版本写出来

2.1 双重循环的完整实现

哪怕是面试，我也建议先把暴力解写出来。它是最直接的“题意翻译”：对每个位置 i，遍历整个数组，把所有j != i的元素乘起来。Java 代码如下：

public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] answer = new int[n]; for (int i = 0; i < n; i++) { int product = 1; for (int j = 0; j < n; j++) { if (j != i) { product *= nums[j]; } } answer[i] = product; } return answer; }

稍微优化一点可以不用判断，直接分成两段累乘，省掉每次循环的if分支：

for (int i = 0; i < n; i++) { int product = 1; for (int j = 0; j < i; j++) { product *= nums[j]; } for (int j = i + 1; j < n; j++) { product *= nums[j]; } answer[i] = product; }

两段累乘在时间量级上和带判断的版本一样，但更贴合“除自己以外”的语义，也方便和后面的左右乘积法对照。

2.2 时间复杂度：n 为 10^5 时会慢到什么程度

暴力解的时间复杂度是 O(n²)。题目给出的数组最长可达 10⁵，10⁵ 的平方是 10¹⁰，这个量级的运算在一秒内基本不可能完成（普通 JVM 每秒大概能执行 10⁸ 到 10⁹ 次简单整数运算，10¹⁰ 次乘法必然超时）。所以暴力解在 LeetCode 上无法通过，但它依然有不可替代的价值。

2.3 暴力解的三重价值

第一，验证你的题意理解。如果暴力输出的示例都对不上，后面优化再漂亮也没用。第二，作为对拍的“参考答案”。优化版本写完后，用随机小数组分别跑暴力版和优化版，逐一对比结果，可以快速发现边界错误。第三，面试表达。面试官想看的是“你能从朴素方案出发，逐步意识到瓶颈并在提示或引导下优化”，而不是直接背出最优解。我面试别人时，候选人如果能先给出暴力解并说明“这版时间复杂度太高”，再往下走，印象分会好很多。

3. 左右乘积数组：把“整体乘积”拆成“左侧积 × 右侧积”

3.1 前缀积与后缀积的递推关系

定义两个辅助数组：

• left[i]表示nums[0]到nums[i-1]的乘积，也就是 i 左侧所有元素的乘积；
• right[i]表示nums[i+1]到nums[n-1]的乘积，也就是 i 右侧所有元素的乘积。

边界上，left[0]没有任何左侧元素，是空乘积，约定为 1；right[n-1]同理约定为 1。为什么空乘积是 1？因为 1 是乘法的单位元，任何数乘以 1 保持不变，这样递推公式在边界处依然成立。

递推关系非常自然：

left[i] = left[i-1] * nums[i-1] right[i] = right[i+1] * nums[i+1]

以left为例，从 i=1 开始，left[1] = left[0] * nums[0] = nums[0]；left[2] = left[1] * nums[1] = nums[0] * nums[1]。一次正向遍历就能把所有位置的左侧积全部算好。right同理，从 n-2 开始反向遍历即可。

3.2 两个辅助数组的 Java 实现

public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] left = new int[n]; int[] right = new int[n]; left[0] = 1; for (int i = 1; i < n; i++) { left[i] = left[i - 1] * nums[i - 1]; } right[n - 1] = 1; for (int i = n - 2; i >= 0; i--) { right[i] = right[i + 1] * nums[i + 1]; } int[] answer = new int[n]; for (int i = 0; i < n; i++) { answer[i] = left[i] * right[i]; } return answer; }

到这里，时间复杂度已经降到 O(n)，额外空间是 O(n)。这个版本在 LeetCode 上可以 AC，很多人的刷题之旅也就停在了这一版。但它还有优化空间，而且面试官大概率会追问。

3.3 正确性依据与直观表格验证

为什么left[i] * right[i]一定等于题目要求的乘积？因为“除nums[i]之外的所有元素”这个集合，恰好被nums[i]一分为二：左边全部、右边全部。集合求积满足结合律和交换律，先算左边的积、再算右边的积、最后乘在一起，和“一次性把集合里所有数乘起来”在数学上是等价的。这个结论不看具体元素，所以负数、0、重复数字都不影响。

用[1,2,3,4]走一遍：

和题目输出完全一致。这个表格也顺带说明了：如果能把left或right中的一个数组“省掉”，空间复杂度就能再降一档。

4. 空间 O(1) 的终极优化：answer 数组先写左积，再被右积补全

4.1 从“两个辅助数组”到“只用输出数组”

上一节里，answer[i]需要同时拿到left[i]和right[i]。如果保留两个辅助数组，空间就是 O(n)。但仔细想一下：left数组的作用只是把左侧积暂存下来，等right也准备好之后做一次乘法。能不能让answer自己先扮演left的角色？

完全可以。第一遍从左往右扫描时，直接把左侧积写进answer[i]：

answer[0] = 1; for (int i = 1; i < n; i++) { answer[i] = answer[i - 1] * nums[i - 1]; }

此时answer数组的内容就是left数组的内容，辅助数组left被“合并”掉了。

4.2 两遍扫描的核心逻辑与“不污染”的原因

接着处理右侧积。维护一个变量right，初始化为 1，表示“从最右边开始累积的右侧乘积”。从i = n-1一直扫到i = 0，每轮做两件事：

answer[i] = answer[i] * right; right *= nums[i];

第一件事把当前答案补上右侧积；第二件事更新right，让它成为下一个位置（i-1）的右侧积。

可能有人会担心：answer里存的左侧积会不会在更新过程中被“污染”？不会。关键在扫描方向是从右往左：answer[i]被乘上right变成最终值之后，后续循环不会再访问answer[i]；而接下来要用的answer[i-1]仍保留着纯左侧积，没有被碰过。所以“就地覆盖”是完全安全的。这个手法在算法里有一个更大的名字叫“原地复用前置结果”，是空间优化的常见套路。

如果还觉得绕，可以用一个类比：第一遍相当于每个人先在纸上写下“我左边所有人的乘积”；第二遍从队伍最右边开始，每个人手里拿着一个“右边所有人的乘积”的牌子，挨个走到左边，把牌子上的数和纸上的数相乘，然后再把自己的数乘进牌子里传给下一个人。

4.3 完整代码与手动走查

完整实现：

public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] answer = new int[n]; // 第一遍：answer[i] 先存左侧积 answer[0] = 1; for (int i = 1; i < n; i++) { answer[i] = answer[i - 1] * nums[i - 1]; } // 第二遍：用滚动变量 right 补全右侧积 int right = 1; for (int i = n - 1; i >= 0; i--) { answer[i] = answer[i] * right; right *= nums[i]; } return answer; }

用[1,2,3,4]手动走查一遍。第一遍结束后：

answer = [1, 1, 2, 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 right = 24 × 1 = 24

最终answer = [24, 12, 8, 6]，正确。时间复杂度 O(n)（两遍线性扫描），额外空间 O(1)（answer是题目要求的输出，不计入额外空间）。这就是这道题在 Java 下的标准最优解。LeetCode 官方题解里的“空间复杂度 O(1)”写法，和这个基本一致。

5. 边界条件与面试追问：零元素、单元素、溢出、除法变体

5.1 零元素的处理

带 0 的用例是[-1,1,0,-3,3]，期望输出[0,0,9,0,0]。用最终优化版跑一次：第一遍算出左侧积，第二遍从右往左乘右侧积，整个过程中 0 只是参与乘法的一个普通元素，把某些位置的积变成 0，不需要任何特殊分支。这也是左右乘积法比除法方案优雅的地方——它把“0 的分布”这个问题直接消解掉了。

5.2 单元素与空数组的防御性写法

LeetCode 的数据保证了nums.length >= 2，所以刷题时可以不用管单元素情况。但面试时主动提边界能加分，工程上更需要防御。一个稳妥写法：

public int[] productExceptSelf(int[] nums) { if (nums == null || nums.length == 0) { return new int[0]; } if (nums.length == 1) { return new int[]{1}; // 空乘积约定为 1 } // 正式逻辑... }

注意 n=1 时按定义是“除 nums[0] 外所有元素的乘积”，也就是空乘积 1。很多人在这一步会写成返回原数组，语义上其实是错的。

5.3 如果面试官允许你用除法

这是一个很常见的追问。允许除法时，思路换成“总乘积剔除当前元素”：

public int[] productExceptSelfWithDivision(int[] nums) { int n = nums.length; int[] answer = new int[n]; int total = 1; int zeroCount = 0; int zeroIndex = -1; for (int i = 0; i < n; i++) { if (nums[i] == 0) { zeroCount++; zeroIndex = i; } else { total *= nums[i]; } } if (zeroCount >= 2) { // 所有答案都是 0 return answer; } if (zeroCount == 1) { answer[zeroIndex] = total; return answer; } for (int i = 0; i < n; i++) { answer[i] = total / nums[i]; } return answer; }

分类的依据是 0 的个数：没有 0，直接除；恰好一个 0，只有那个位置是“其余元素的乘积”，其他位置全是 0；至少两个 0，全部是 0。这个版本的代码明显比左右乘积法啰嗦，而且每一步都要考虑除零风险。这恰好能解释为什么题目要禁除法——不是不能用，而是“总乘积 + 除法”这一思路在数据分布稍微复杂一点时就会变得脆弱，远不如“左右拆分”干净。

5.4 整型溢出的隐患与稳妥做法

题目保证最终答案在 32 位有符号整数范围内，所以主流题解的int写法可以直接通过。但严格来说，中间过程不一定安全：例如数组里某个位置的右侧积为 0，最终答案会变成 0，而左侧积本身可能非常大。如果两侧的中间乘积超过Integer.MAX_VALUE，用int累积就会溢出。LeetCode 官方的测试数据没有触发这类情况，但在工程思维里这是一个不能忽略的风险点。

稳妥的做法是把累积变量换成long：

long[] answer = new long[n]; // 或者内部使用 long 累积，最后强转 int

如果题目要求返回int[]，可以在最后强转，并在注释里说明依赖题目保证。更极端的场景（元素值巨大、结果超过 64 位）就只能用BigInteger或者取模运算，那就是另一套考点了。面试时提到这一点，会显得你不是只会抄题解。

5.5 面试官真正想看的三件事

我面过不少候选人，出这题时主要看三点：第一，能不能从“全局除法”切换到“左右拆分”，这是思路的拐点；第二，能不能在没有提示的情况下完成空间优化，这反映你对“数组被复用后值的含义”是否敏感；第三，能不能主动讨论 0 和溢出，这是考察工程意识。如果你只是想背代码，这三关都过不了。所以刷题的时候，建议把暴力、双数组、单变量三个版本都亲手写一遍，把差异想透。

6. 把“前缀积/后缀积”的套路迁移到其他地方

6.1 前缀和与前后缀信息的家族题目

这道题的核心手法是“预计算前缀/后缀信息，再在 O(1) 时间内回答每个位置的问题”。前缀思想在 LeetCode 里非常常见，最基础的是前缀和：

• LeetCode 303 区域和检索：preSum[i]表示前 i 个元素之和，区间和sum[left, right]就能用preSum[right+1] - preSum[left]得到；
• LeetCode 724 寻找数组的中心下标：求一个位置使左右和相等，可以先求总和，再从左往右累加，判断leftSum == total - leftSum - nums[i]；
• LeetCode 560 和为 K 的子数组：把前缀和存进哈希表，一趟遍历完成统计。

和本题关系最紧密的是 724，它同样需要“左半边信息 + 右半边信息”的组合。掌握了“排除自身”这种套路，这些题看起来会有一层相同的底色。

6.2 工程场景中的“排除自身”统计

很多人觉得算法题和业务开发是两座孤岛。我自己在数据相关项目里见过这类问题的工程版：比如风控系统要计算某个交易指标时，需要判断“如果把当前样本剔除，整体的均值或方差会不会发生显著变化”，这时就需要快速得到“除当前样本外的聚合值”。数据量小直接双重循环无所谓，但到百万级样本就必须用前缀/后缀累计值配合运算。再比如推荐系统里给物品打分做归一化时，有时也需要每个位置排除自身后的分母。前缀累积这个思路，在离线计算和流式计算里都有对应实现。

如果只记住一句话，我的总结是：当一个数组里每个位置的答案都依赖于“其他位置”的整体信息时，先看看能不能把整体拆成“左侧 + 右侧”，分别预计算再合并。这个想法从这道题出发，可以延伸到一大片题目和真实系统。

我在刷题和面试里反复和这道题打交道，最深的感觉是：最优解的记忆成本其实很低，难的是理解它为什么这样设计。建议你照着三个版本各写一遍，再用随机数组把暴力版和最终版跑一个对拍，确认全绿之后，这道题才算真正吃透了。后续再遇到任何“排除自身”型的问题，你会第一时间想起这个左右拆分的套路。