本文详解「除自身以外数组的乘积」问题的双遍历前缀/后缀乘积解法，通过两次线性扫描构造答案数组，避免使用除法且满足 o(1) 额外空间（不计输出数组），并逐步解析执行过程与关键细节。

本文详解「除自身以外数组的乘积」问题的双遍历前缀/后缀乘积解法，通过两次线性扫描构造答案数组，避免使用除法且满足 o(1) 额外空间（不计输出数组），并逐步解析执行过程与关键细节。

在 LeetCode 第 238 题 Product of Array Except Self 中，要求对给定整数数组 nums，返回一个新数组 ans，其中 ans[i] 表示 除 nums[i] 外所有元素的乘积，且禁止使用除法、时间复杂度需为 O(n)，空间复杂度理想为 O(1)（输出数组不计入）。

核心思想是：每个位置 i 的结果 = i 左侧所有元素乘积 × i 右侧所有元素乘积。我们用两次遍历分别计算这两部分，并直接复用答案数组 ans 存储中间结果，实现空间优化。

✅ 第一次遍历（从左到右）：计算左侧乘积（prefix）

初始化 pre = 1，ans[i] 在此阶段仅存 nums[0] × nums[1] × … × nums[i−1]（即 i 左侧所有数的乘积）：

int pre = 1;
for (int i = 0; i < nums.length; i++) {
    ans[i] = pre;     // ans[i] = 左侧乘积（初始为1，故 ans[0] = 1）
    pre *= nums[i];   // 更新 prefix，供下一位置使用
}

以 nums = [1, 2, 3, 4] 为例，逐步执行：

• i=0：ans[0] = 1，pre = 1×1 = 1
• i=1：ans[1] = 1，pre = 1×2 = 2
• i=2：ans[2] = 2，pre = 2×3 = 6
• i=3：ans[3] = 6，pre = 6×4 = 24
  ✅ 得到：ans = [1, 1, 2, 6]

⚠️ 注意：不是 [1,2,6,24] —— 因为 ans[i] 赋值发生在 pre 更新之前，所以它永远保存的是“当前位置左侧”的累积乘积，不包含 nums[i] 自身。

✅ 第二次遍历（从右到左）：累乘右侧乘积（postfix）

初始化 post = 1，从末尾反向遍历，每次将 ans[i] 乘以当前 post（即 nums[i+1] × … × nums[n−1]），再更新 post：

int post = 1;
for (int i = nums.length - 1; i >= 0; i--) {
    ans[i] *= post;   // ans[i] = 左侧乘积 × 右侧乘积
    post *= nums[i];  // 扩展 postfix，包含当前 nums[i]
}

继续 nums = [1,2,3,4]，此时 ans = [1,1,2,6]，post 初始为 1：

• i=3：ans[3] = 6 × 1 = 6，post = 1×4 = 4
• i=2：ans[2] = 2 × 4 = 8，post = 4×3 = 12
• i=1：ans[1] = 1 × 12 = 12，post = 12×2 = 24
• i=0：ans[0] = 1 × 24 = 24，post = 24×1 = 24
  ✅ 最终：ans = [24, 12, 8, 6] —— 完全匹配预期输出。

? 关键总结

• 零空间开销：仅用 pre 和 post 两个变量，无额外数组；
• 无除法依赖：天然规避了除零异常和浮点精度问题；
• 可扩展性强：该模式适用于多种“排除自身影响”的累积类问题（如和、异或等）；
• 边界自然处理：首元素左侧无元素 → pre=1；末元素右侧无元素 → post=1，逻辑简洁鲁棒。

掌握这一“分治式前缀/后缀累积”思维，是解决数组类高频面试题的重要基石。