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] = 前缀乘积 × 后缀乘积（左边所有数的积 × 右边所有数的积 = 除自身外所有数的积）。