除自身以外数组的乘积：前后缀分离的O(1)空间技巧

适读人群：Java 开发者、准备算法面试的工程师 | 阅读时长：约18分钟 | 难度：Medium

---

开篇故事

这道题我第一次在面试里被问到，是 2020 年面一家金融科技公司。题目刚出来我就想到了"用全部乘积除以 nums[i]"，花了不到一分钟说完这个思路。面试官微微点头，然后问："不用除法怎么做？"

我一愣。限制不能用除法，这道题还能怎么做？当时在白板上想了大概两分钟，想到了可以用"左边所有数的乘积 × 右边所有数的乘积"，也就是前缀积和后缀积。面试官再问："能不能不用额外数组？"

这个追问让我当场懵了——要同时维护左积和右积而不用额外数组，怎么操作？后来面试结束后我仔细想了想，发现是可以的：先从左到右把前缀积存在结果数组里，再从右到左用一个变量维护后缀积，边遍历边把结果数组的前缀积乘上后缀积。结果数组本身被重复利用了，不算"额外"空间。

这道题是考察"前后缀分离"思想的经典题目，而这个思想在多道题目里都有用武之地（接雨水、股票买卖都用到了类似的"左边看过的最大值"和"右边看过的最大值"）。

---

一、题目解析

LeetCode 238. 除自身以外数组的乘积（Product of Array Except Self）

给你一个整数数组 nums，返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

进阶： 你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

输入输出示例：

示例 1（基础情况）：

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

示例 2（含零）：

输入：nums = [-1,1,0,-3,3]
输出：[0,0,9,0,0]

边界情况 3（两个零）：

输入：nums = [0,0,2,3]
输出：[0,0,0,0]
解释：只要有两个0，所有位置的乘积都是0

边界情况 4（一个零）：

输入：nums = [1,2,0,4]
输出：[0,0,8,0]
解释：只有 nums[2]=0 的位置，乘积是其他三个数的积；其他位置因为包含了 0，乘积为 0

考察的核心知识点：

• 不用除法实现"除自身以外的乘积"
• 前缀积和后缀积的分离计算
• 用结果数组复用替代额外的后缀积数组

---

二、解法一：暴力解法（含除法，仅供理解）

思路分析

统计数组中零的个数：

• 两个及以上的零：所有位置结果都是 0
• 恰好一个零：只有零所在位置的结果是非零数（其他所有元素的积），其他位置都是 0
• 没有零：每个位置结果 = 总乘积 / nums[i]

但题目明确说不能用除法。这个解法只是帮助理解，不能用于提交。

// 含除法的版本（不满足题目要求，仅供理解）
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int zeroCount = 0;
        long totalProduct = 1;
        for (int num : nums) {
            if (num == 0) zeroCount++;
            else totalProduct *= num;
        }
        
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            if (zeroCount >= 2) result[i] = 0;
            else if (zeroCount == 1) result[i] = (nums[i] == 0) ? (int) totalProduct : 0;
            else result[i] = (int) (totalProduct / nums[i]);
        }
        return result;
    }
}

时间复杂度：O(n)，但因为用了除法，不满足题目要求。

---

三、解法二：前缀积+后缀积数组（O(n) 空间）

优化思路

answer[i] = 左边所有数的乘积 × 右边所有数的乘积

预计算：

• leftProduct[i] = nums[0] × nums[1] × ... × nums[i-1]（不含 i）
• rightProduct[i] = nums[i+1] × nums[i+2] × ... × nums[n-1]（不含 i）

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] leftProduct = new int[n];
        int[] rightProduct = new int[n];
        int[] answer = new int[n];
        
        // 计算前缀积：leftProduct[i] = nums[0..i-1] 的乘积
        leftProduct[0] = 1;
        for (int i = 1; i < n; i++) {
            leftProduct[i] = leftProduct[i - 1] * nums[i - 1];
        }
        
        // 计算后缀积：rightProduct[i] = nums[i+1..n-1] 的乘积
        rightProduct[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            rightProduct[i] = rightProduct[i + 1] * nums[i + 1];
        }
        
        // 合并：answer[i] = leftProduct[i] * rightProduct[i]
        for (int i = 0; i < n; i++) {
            answer[i] = leftProduct[i] * rightProduct[i];
        }
        
        return answer;
    }
}

时间复杂度：O(n)，三次线性遍历。

空间复杂度：O(n)，两个辅助数组（不算输出数组）。

---

四、解法三：O(1) 额外空间（工业级最优解）

核心洞见

O(1) 空间的关键：不需要同时存储前缀积和后缀积两个数组。可以先用输出数组存前缀积，再用一个变量从右往左维护后缀积，边走边更新输出数组。

步骤：

1. 先从左到右遍历，将前缀积存入 answer
2. 再从右到左遍历，用变量 R 维护当前位置右侧的累积乘积，更新 answer[i] = answer[i] * R，然后 R *= nums[i]

算法流程

完整 Java 代码

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        
        // 第一步：从左到右，answer[i] 存放 nums[0..i-1] 的乘积（前缀积）
        answer[0] = 1;
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i - 1] * nums[i - 1];
        }
        // 此时 answer = [1, nums[0], nums[0]*nums[1], ...]
        
        // 第二步：从右到左，用变量 R 维护右侧累积乘积（后缀积）
        int R = 1;  // R = nums[i+1..n-1] 的乘积，初始为 1（空乘积）
        for (int i = n - 1; i >= 0; i--) {
            // answer[i] 当前存的是前缀积，乘上后缀积 R，就得到了最终答案
            answer[i] *= R;
            // 更新 R：把 nums[i] 加入后缀积，供下一个（左边的）位置使用
            R *= nums[i];
        }
        
        return answer;
    }
}

复杂度分析

时间复杂度：O(n)

两次线性遍历，每次遍历 O(n)，总体 O(n)。

空间复杂度：O(1)（不算输出数组）

只用了一个变量 R，是真正的 O(1) 额外空间。

我在 LeetCode 提交，运行时间 1ms，击败 99.9% 的 Java 用户，内存 51MB，击败 95% 以上。

---

五、举一反三

同类型题目

LeetCode 42. 接雨水（双指针版本）

每个位置的接水量 = min(左边最大, 右边最大) - 当前高度。"左边最大"是前缀最大值，"右边最大"是后缀最大值，和本题的前缀积/后缀积思路完全对称。

LeetCode 121. 买卖股票的最佳时机

最大利润 = 右边最大价格 - 左边最小价格。从左维护最小值，从右维护最大值，本质上也是前后缀分离思想。

LeetCode 1. 两数之和（最近最大乘积差）

找两对数，使乘积差最大：(a×b - c×d)，其中 a,b,c,d 各不同。

LeetCode 724. 寻找数组的中心下标

找下标 i，使得左边元素之和等于右边元素之和。前缀和 + 后缀和，同样的前后缀分离思路。

前后缀分离通用思路

遇到"每个位置的结果依赖左边某种状态和右边某种状态"的题目，都可以考虑前后缀分离：

1. 预计算左侧的累积信息（从左到右）
2. 实时维护右侧的累积信息（从右到左）
3. 两者合并得到每个位置的答案

空间优化思路：先把左侧信息存入输出数组，再用变量维护右侧信息，一边更新一边合并。

面试中的变体和追问

1. 不用额外数组的关键是什么？ 答：关键是两次遍历可以分开，第一次遍历的结果（前缀积）可以临时存在输出数组里，第二次遍历时直接原地更新，所以只需要一个变量维护后缀积。

2. 如果 nums 里有 0 怎么处理？ 答：这个解法不需要特殊处理 0。前缀积和后缀积的乘法天然处理了 0 的传播：0 存在时乘积为 0，不存在时乘积非 0。

3. 数组长度为 1 时怎么处理？ 答：长度为 1 时，"除自身以外"的乘积是空乘积，结果是 1（乘法单位元）。代码里 answer[0] = 1，第二步 R=1，answer[0] *= 1，返回 [1]，正确。

---

六、踩坑实录

坑一：前缀积和后缀积的边界初始化

现象： 结果数组第一个或最后一个元素不对。

原因： leftProduct[0] 应该是 1（空乘积，nums[0] 左边没有元素），rightProduct[n-1] 应该是 1（nums[n-1] 右边没有元素）。如果初始化成其他值，整个乘积链都会出错。

解法： 始终记住：空乘积 = 1（数学上的约定，乘法单位元）。

坑二：从右到左更新 R 的顺序

现象： 最终某些位置结果不对，尤其是末尾。

原因： 在第二次遍历时，顺序很重要：先用 R 更新 answer[i]，再把 nums[i] 乘入 R。如果先把 nums[i] 乘入 R，那么 R 就包含了 nums[i]，answer[i] 就把自己也乘进去了，出错。

// 错误顺序
R *= nums[i];     // 先更新 R（包含了 nums[i]）
answer[i] *= R;   // 再用 R 更新 answer，但 R 已经包含 nums[i] 了，错误！

// 正确顺序
answer[i] *= R;   // 先用当前 R（不含 nums[i]）更新 answer
R *= nums[i];     // 再把 nums[i] 加入 R，供下一个位置（左边）使用

坑三：整数溢出

现象： 当数组很长且元素绝对值较大时，乘积溢出 int 范围。

原因： 题目说"任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内"，所以理论上不会溢出，但面试里如果面试官说"不保证不溢出怎么处理"，答案是换用 long 类型：

long R = 1;
long[] answer = new long[n];

---

七、总结

这道题的精髓在于"前后缀分离"和"原地复用输出数组"两个技巧。前者是解题思路，后者是空间优化手段。

三条核心要点：

1. "除自身以外的乘积"= 左侧所有数的乘积 × 右侧所有数的乘积。这个分解把一个 O(n²) 的枚举转化成了两次 O(n) 的遍历。

2. O(1) 空间的关键：先用输出数组临时存放前缀积，再用单变量维护后缀积，两次遍历完成所有计算，输出数组不算额外空间。

3. 更新顺序要正确：第二次从右到左遍历时，先用 R 更新 answer[i]，再把 nums[i] 乘入 R。顺序不能颠倒。

延伸思考：

前后缀分离是一个思维框架，适用于"每个位置的值依赖其左边历史和右边历史"的题目。遇到这类题，先想能否独立计算左侧状态和右侧状态，再考虑合并。这个框架在接雨水、买卖股票、区域和等题里都有体现。