LeetCode238这道题非常考察前缀/后缀预处理思维以及空间优化能力，是线性DP和数组操作的经典入门题，请务必在不看代码的情况下，自己在草稿纸上画出那个 $L$ 和 $R$ 的表格，并手写一遍代码！

---

一、 题目描述

题目名称： 除自身以外数组的乘积 (Constructing the Product Array)

题目描述： 给定一个长度为 $n$ 的整数序列 $A = \{a_1, a_2, \dots, a_n\}$。 请你构建并输出一个同样长度的序列 $B = \{b_1, b_2, \dots, b_n\}$。 其中，$b_i$ 等于序列 $A$ 中除 $a_i$ 之外所有元素的乘积。

要求：

1. 严禁使用除法。
2. 算法的时间复杂度必须为 $O(n)$。
3. （进阶挑战）尝试将额外空间复杂度优化至 $O(1)$（输出数组占用的空间不计入额外空间）。

【输入格式】 第一行包含一个正整数 $n$，表示序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示序列 $A$ 的元素，相邻元素之间用空格分隔。

【输出格式】 输出一行，包含 $n$ 个整数，表示构建的序列 $B$，相邻元素之间用空格分隔。

【样例数据 1】 输入：

4
1 2 3 4

输出：

24 12 8 6

【样例数据 2】 输入：

5
-1 1 0 -3 3

输出：

0 0 9 0 0

【数据范围与提示】

• 对于 $100\%$ 的数据，满足 $2 \le n \le 10^5$。
• 对于 $100\%$ 的数据，满足 $-30 \le a_i \le 30$。
• 保证任意前缀或后缀的乘积以及最终结果都在 32 位有符号整数范围内。

---

二、 预备知识点

解决这道题，你需要掌握以下“武器”：

1. 基础数组操作：遍历、索引访问。
2. 前缀和/前缀积 (Prefix Sum/Product)：理解如何利用数组预处理，快速得到区间 $[1, i]$ 的运算结果。
3. 后缀和/后缀积 (Suffix Sum/Product)：与前缀积对称，理解如何快速得到区间 $[i, n]$ 的运算结果。
4. 空间复杂度分析：理解什么是“原地算法 (In-place algorithm)”，区分输入/输出空间与辅助空间。

---

三、 关键词与审题陷阱

做题先审题，看到这道题，你的雷达应该扫描到以下关键词：

1. “除 nums[i] 之外”：

   • 这意味着 $b_i = a_1 \times \dots \times a_{i-1} \times a_{i+1} \times \dots \times a_n$。
   • 直观反应：是不是算出总乘积 $P$，然后 $b_i = P / a_i$？

2. “不要使用除法”：

   • 警报！ 这是出题人故意封死了最简单的路。
   • 为什么？除了考察算法能力外，如果数组中有 $0$，除法会报错；或者如果数字极大需要取模，除法需要求逆元，复杂度就变了。虽然这题数据范围小，但规则就是规则。

3. “$O(n)$ 时间”：

   • 意味着不能写双重循环（$O(n^2)$），必须遍历常数次数组解决问题。

在做此类题时，如何快速提取关键信息？

1. “除自身以外” + “乘积/和”：

   • 反射弧：立刻想到前缀处理 + 后缀处理。
   • 这是一个经典的“拼图”模型，中间空一块，两边拼起来。

2. “不能使用除法”：

   • 警示：封死了 $Total / a[i]$ 的捷径。
   • 暗示：这题考察的是构造能力，而不是简单的数学运算。同时也为了避免“除零错误”。

3. “$O(n)$ 时间” + “$O(1)$ 空间”：

   • 暗示：不要试图嵌套循环，不要开多余的数组。
   • 技巧：复用输入或输出数组作为中间存储容器。

---

四、 启发式教学：草稿纸上的推理演练

现在，拿出你的草稿纸，我们来画图推导。

阶段一：暴力直觉（不可行，但有助于理解）

假设 $A = [2, 3, 4, 5]$。 我们要算 $b_2$ (对应原数组的 3)，也就是算 $2 \times 4 \times 5$。 如果每个都遍历一遍去乘，总共要 $N$ 次，每次操作 $N$ 次，复杂度 $O(N^2)$。超时 (TLE)。

阶段二：图形化拆解（引入前缀与后缀）

让我们把 $b_i$ 的构成拆解一下。看看 $b_i$ 是由哪两部分组成的？ 以 $i=3$ 为例（数组下标从1开始）：

$$A = [\mathbf{a_1, a_2}, \mathbf{a_3}, \mathbf{a_4, a_5}] $$$$b_3 = (\mathbf{a_1 \times a_2}) \times (\mathbf{a_4 \times a_5}) $$

发现了吗？

$$b_i = (a_i \text{ 左边所有数的乘积}) \times (a_i \text{ 右边所有数的乘积}) $$

我们可以在草稿纸上画个表格：

索引 $i$	左边部分 ($L_i$)	右边部分 ($R_i$)	最终结果 ($L_i \times R_i$)
1	无 (设为1)	$a_2 \dots a_n$	$1 \times (a_2 \dots a_n)$
2	$a_1$	$a_3 \dots a_n$	$a_1 \times (a_3 \dots a_n)$
3	$a_1 \times a_2$	$a_4 \dots a_n$	$(a_1 a_2) \times (a_4 \dots a_n)$
...
$n$	$a_1 \dots a_{n-1}$	无 (设为1)	$(a_1 \dots a_{n-1}) \times 1$

策略：

1. 如果我们能先算出所有的 $L_i$（前缀积）。
2. 再算出所有的 $R_i$（后缀积）。
3. 把它们对应位相乘，不就得到答案了吗？

构造 $L$ 数组： $L_1 = 1$ $L_2 = L_1 \times a_1$ $L_3 = L_2 \times a_2$ ... 递推公式： $L_i = L_{i-1} \times a_{i-1}$

同理构造 $R$ 数组： $R_n = 1$ $R_{n-1} = R_n \times a_n$ ... 递推公式： $R_i = R_{i+1} \times a_{i+1}$

复杂度分析：

• 时间：计算 $L$ 需 $O(n)$，计算 $R$ 需 $O(n)$，最后相乘 $O(n)$。总计 $O(n)$。达标！
• 空间：需要两个辅助数组 $L$ 和 $R$，空间 $O(n)$。

阶段三：空间优化（冲击金牌思维）

题目有一个进阶要求：额外空间 $O(1)$。 目前我们用了两个数组 $L$ 和 $R$。 思考： 我们真的需要把 $L$ 和 $R$ 都完整存下来吗？

优化步骤：

1. 利用答案数组： 题目允许返回一个数组，这个空间不计入额外空间。我们可以先用 ans 数组来存储 $L$（前缀积）。
   • 此时：ans[i] 里面存的是 $i$ 左边的积。
2. 动态计算后缀积： 我们可以倒着遍历数组（从右向左）。
   • 用一个变量 R_acc (Right Accumulator) 来记录当前 $i$ 右边的乘积。
   • 在倒序遍历时，直接计算 ans[i] = ans[i] * R_acc。
   • 然后更新 R_acc = R_acc * a[i]。

图解过程： 输入：[2, 3, 4]

Step 1: 算前缀积存入 ans ans 初始化：[1, 1, 1] $i=0$: ans[0] = 1 $i=1$: ans[1] = ans[0] * a[0] = 1 * 2 = 2 $i=2$: ans[2] = ans[1] * a[1] = 2 * 3 = 6 此时 ans 状态：[1, 2, 6] (代表左侧乘积)

Step 2: 倒序乘入后缀积 (维护变量 R) R = 1 $i=2$: ans[2] = ans[2] * R = 6 * 1 = 6。更新 R = R * a[2] = 1 * 4 = 4。 $i=1$: ans[1] = ans[1] * R = 2 * 4 = 8。更新 R = R * a[1] = 4 * 3 = 12。 $i=0$: ans[0] = ans[0] * R = 1 * 12 = 12。更新 R (结束可不更)。

最终 ans: [12, 8, 6]。答案正确！ 空间复杂度： 仅使用了一个变量 R，额外空间 $O(1)$。

---

五、 OI风格参考代码 (C++14)

/*
 * Problem: Product of Array Except Self (OI Version)
 * Approach: Prefix and Suffix Products with O(1) Extra Space
 * Time Complexity: O(N)
 * Space Complexity: O(1) (Auxiliary)
 */

#include <bits/stdc++.h>

using namespace std;

// 使用 fast I/O 是 OI 选手的基本素养
void solve() {
    int n;
    if (!(cin >> n)) return;

    // 根据数据范围，使用 vector 动态开辟，防止栈溢出
    // 虽然 n <= 10^5 可以开静态全局数组，但 vector 更符合现代 C++ 风格
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    // ans 数组用于存储结果
    // 同时也先作为“前缀积”的容器
    vector<int> ans(n);

    // 1. 先计算前缀积 (Left Products)
    // ans[i] 表示 nums[0]...nums[i-1] 的乘积
    ans[0] = 1; // 第一个元素左边没有数字，视为 1
    for (int i = 1; i < n; ++i) {
        ans[i] = ans[i - 1] * nums[i - 1];
    }

    // 2. 动态计算后缀积并更新结果 (Right Products)
    // 使用一个变量 R 来记录右边所有数的乘积，节省空间
    int R = 1; // 最右边元素右边没有数字，视为 1
    for (int i = n - 1; i >= 0; --i) {
        // 当前格子的最终结果 = (左边积) * (右边积)
        ans[i] = ans[i] * R;
        
        // 更新 R，包含当前元素，供下一个位置（即左边一位）使用
        R = R * nums[i];
    }

    // 3. 输出结果
    for (int i = 0; i < n; ++i) {
        cout << ans[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;
}

int main() {
    // 关闭同步流，加速输入输出
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    solve();
    
    return 0;
}

六、 总结与课后思考

1. 核心思想：将“除去自己”转化为“左边 $\times$ 右边”。
2. 思维定势打破：看到乘积不一定要想除法，特别是题目禁止时，要想到构造法。
3. 空间换时间 vs 时间换空间：最开始 $O(N)$ 空间、$O(N)$ 时间的解法是基础，利用输出数组复用空间是高级技巧。
4. 举一反三：
   • 如果题目改成“除自己之外的所有元素之和”，怎么做？（非常简单，可以用总和减当前，也可以用前缀和+后缀和）。
   • 如果题目允许除法，但是数组里可能有 0，该怎么处理？（统计 0 的个数：0个0 -> 正常除；1个0 -> 只有0的那个位置是非0，其他全0；>1个0 -> 全0）。

希望这个思路能帮你在草稿纸上理清逻辑，这就是金牌选手解题的第一步！

---

思维过程附加讲解

1. 拆解问题：图形化分析

我们要算 $b_i$（除自己外的乘积），实际上就是把 $a_i$ 挖掉，左边的乘积 $\times$ 右边的乘积。

画个图（以样例1 [1, 2, 3, 4] 为例）：

索引 $i$	原数组 $A$	左边部分 (前缀积)	右边部分 (后缀积)	$b_i$ (左 $\times$ 右)
1		无 (默认为1)	$2 \times 3 \times 4 = 24$	$1 \times 24 = 24$
2		$1$	$3 \times 4 = 12$	$1 \times 12 = 12$
3		$1 \times 2 = 2$	$4$	$2 \times 4 = 8$
4		$1 \times 2 \times 3 = 6$	无 (默认为1)	$6 \times 1 = 6$

结论：$b_i = \text{前缀Prefix}[i-1] \times \text{后缀Suffix}[i+1]$。

2. 初步方案：左右两次扫描 ($O(N)$ 空间)

我们需要两个辅助数组 L[] 和 R[]。

• L[i] 存 $a_i$ 左边的积。
• R[i] 存 $a_i$ 右边的积。
• 最后 ans[i] = L[i] * R[i]。

这很简单，但需要 $3N$ 的空间（L数组+R数组+答案数组）。

3. 进阶方案：空间折叠 ($O(1)$ 辅助空间)

提问：我们真的需要把 L 和 R 都存下来吗？

• 第一步：我们可以直接把 L（前缀积）存到答案数组 ans 里！因为计算 $b_i$ 时，我们只需要 $i$ 左边的积，算完存进去不冲突。
• 第二步：那 R（后缀积）怎么办？我们从右往左遍历的时候，R 的值是动态变化的。能不能只用一个变量 right_product 来跟着跑？

推导演示 (草稿纸过程)： 数组 $A = [1, 2, 3, 4]$

Phase 1: 正序遍历，算左边积，存入 ans

• $i=1$: 左边没数 $\rightarrow$ ans[1]=1
• $i=2$: 左边有1 $\rightarrow$ ans[2] = ans[1] * A[1] = 1 * 1 = 1
• $i=3$: 左边有1,2 $\rightarrow$ ans[3] = ans[2] * A[2] = 1 * 2 = 2
• $i=4$: 左边有1,2,3 $\rightarrow$ ans[4] = ans[3] * A[3] = 2 * 3 = 6
• 此时 ans = [1, 1, 2, 6] (这是所有位置的左侧积)

Phase 2: 倒序遍历，维护变量 R，乘入 ans

• 初始 R = 1
• $i=4$: ans[4] = ans[4] * R = 6 * 1 = 6。更新 R = R * A[4] = 1 * 4 = 4。
• $i=3$: ans[3] = ans[3] * R = 2 * 4 = 8。更新 R = R * A[3] = 4 * 3 = 12。
• $i=2$: ans[2] = ans[2] * R = 1 * 12 = 12。更新 R = R * A[2] = 12 * 2 = 24。
• $i=1$: ans[1] = ans[1] * R = 1 * 24 = 24。更新 R = ...
• 最终 ans = [24, 12, 8, 6]。完美！

4. 复杂度分析

• 时间复杂度：正序遍历一次 $O(N)$，倒序遍历一次 $O(N)$。总共 $O(N)$。
• 空间复杂度：只用了 ans 数组（题目允许）和一个变量 R。辅助空间 $O(1)$。