LeetCode Hot100：除自身以外数组的乘积

LeetCode 解题：除自身以外数组的乘积——从暴力到空间最优解

在数组类算法题中，除自身以外数组的乘积 (LeetCode 238) 是一道经典的「前缀 / 后缀乘积」应用题目，也是面试中考察「空间优化思路」的高频题。这道题的核心难点在于：要求时间复杂度 O(n)、空间复杂度 O(1)（输出数组除外），且不能使用除法。

一、问题背景：明确「除自身以外数组的乘积」题目要求

先把题目核心要求讲清楚，这是解题的前提，也是所有解法的目标：给定一个整数数组 nums，返回一个数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余所有元素的乘积。

关键约束（决定解法的核心）

这是本题和普通「乘积计算」的最大区别，也是优化的方向：

1. 时间复杂度必须为 O(n)：不能用双层循环暴力枚举；
2. 空间复杂度尽可能优：进阶要求是 O(1)（输出数组不算入空间复杂度）；
3. 禁止使用除法：不要想着「先算总乘积，再除以每个元素」—— 一方面数组中可能有 0（除法无意义），另一方面题目隐含禁止该思路。

题目示例

输入：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

二、那些「行不通」的思路

拿到这道题，我们很容易想到两种基础思路，但都不符合题目约束：

思路 1：暴力双层 for 循环枚举

遍历每个元素 i，再遍历数组中除 i 外的所有元素计算乘积。

• 优点：思路简单，结果正确；
• 缺点：时间复杂度 O(n²)，数组长度稍大就会超时，不符合 O(n) 要求。

思路 2：总乘积除法

先计算数组所有元素的总乘积，再用总乘积除以 nums[i] 得到 answer[i]。

• 优点：时间复杂度 O(n)，计算高效；
• 缺点：① 数组中有 0 时，除法无意义；② 违反题目「禁止除法」的隐含要求，面试中会被扣分。

既然这两种思路都不行，我们需要找到「不暴力、不用除法、O(n) 时间」的解法 —— 这就是「前缀乘积 + 后缀乘积」的核心思路。

三、核心原理：前缀乘积 & 后缀乘积

这是本题的「解题基石」，理解这两个概念，就等于掌握了本题的核心逻辑：

定义（关键）

1. 前缀乘积：对于位置 i，前缀乘积 是 nums[0] × nums[1] × ... × nums[i-1]（i 左边所有元素的乘积）；
2. 后缀乘积：对于位置 i，后缀乘积 是 nums[i+1] × nums[i+2] × ... × nums[n-1]（i 右边所有元素的乘积）；
3. 最终结果：answer[i] = 前缀乘积 × 后缀乘积（左边所有数的积 × 右边所有数的积 = 除自身外所有数的积）。

示例可视化（一看就懂）

以 nums = [1,2,3,4] 为例，直观感受前缀 / 后缀乘积和结果的关系：

位置 i	nums[i]	前缀乘积（左边积）	后缀乘积（右边积）	answer[i] = 前缀 × 后缀
0	1	1（左边无元素）	2×3×4=24	1×24=24
1	2	1=1	3×4=12	1×12=12
2	3	1×2=2	4=4	2×4=8
3	4	1×2×3=6	1（右边无元素）	6×1=6

四、最优解：空间复用的前缀后缀乘积

相比「单独定义前缀数组 + 后缀数组」的基础解法，本方案复用了后缀数组作为结果数组，并用变量替代前缀数组，将空间复杂度从 O(n) 优化到 O(1)（输出数组不算），完全符合题目进阶要求！

解题思路

整个过程分为两步，核心是「先算后缀乘积，再用变量累加前缀乘积，最后相乘得到结果」，全程只用到一个数组（结果数组）和一个变量，极致优化空间：

阶段 1：计算后缀乘积，存入结果数组

1. 初始化一个数组 suf（最终作为结果数组），长度和 nums 一致；
2. 因为最后一个元素的后缀乘积是 1（右边无元素），所以 suf[nums.length-1] = 1；
3. 从后往前遍历数组（从 nums.length-2 到 0），计算每个位置的后缀乘积：suf[m] = suf[m+1] × nums[m+1]（当前位置的后缀乘积 = 下一个位置的后缀乘积 × 下一个位置的元素）。

阶段 2：累加前缀乘积，计算最终结果

1. 初始化前缀乘积变量 pre = 1（第一个元素的前缀乘积是 1）；
2. 从前往后遍历数组，对每个位置 i：
   • suf[i] = suf[i] × pre（后缀乘积 × 前缀乘积 = 除自身外的乘积）；
   • 更新前缀乘积：pre = pre × nums[i]（把当前元素加入前缀乘积，供下一个位置使用）。
3. 遍历结束后，suf 数组就是最终的结果数组。

思路可视化（以 nums=[1,2,3,4] 为例）

阶段 1：计算后缀乘积

初始：suf = [0,0,0,1]

• m=2 → suf[2] = suf[3]×nums[3] = 1×4=4 → suf = [0,0,4,1]
• m=1 → suf[1] = suf[2]×nums[2] = 4×3=12 → suf = [0,12,4,1]
• m=0 → suf[0] = suf[1]×nums[1] = 12×2=24 → suf = [24,12,4,1]

阶段 2：累加前缀乘积

初始：pre=1

• i=0 → suf[0] = 24×1=24 → pre=1×1=1 → suf = [24,12,4,1]
• i=1 → suf[1] = 12×1=12 → pre=1×2=2 → suf = [24,12,4,1]
• i=2 → suf[2] = 4×2=8 → pre=2×3=6 → suf = [24,12,8,1]
• i=3 → suf[3] = 1×6=6 → pre=6×4=24 → suf = [24,12,8,6]

最终结果：[24,12,8,6]，和示例一致。

完整源码

代码逻辑正确，已补充详细注释，可直接提交 LeetCode 测试。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        // 1. 初始化后缀乘积数组（复用为最终结果数组）
        int[] suf = new int[nums.length];
        // 最后一个元素的后缀乘积为 1（右边无元素）
        suf[nums.length-1] = 1;

        // 2. 从后往前遍历，计算每个位置的后缀乘积
        for(int m = nums.length-2; m >= 0; m--){
            // 当前位置的后缀乘积 = 下一个位置的后缀乘积 × 下一个位置的元素
            suf[m] = suf[m+1] * nums[m+1];
        }

        // 3. 初始化前缀乘积变量（用变量替代前缀数组，节省空间）
        int pre = 1;

        // 4. 从前往后遍历，结合前缀乘积计算最终结果
        for(int i = 0; i < nums.length; i++){
            // 最终结果 = 后缀乘积 × 前缀乘积
            suf[i] *= pre;
            // 更新前缀乘积：把当前元素加入前缀乘积，供下一个位置使用
            pre *= nums[i];
        }

        // 5. 返回结果数组（已复用 suf 数组）
        return suf;
    }
}