--- tags: ["LeetCode", "前缀和", "数组", "中等"] create time: 2026-05-14 13:08 --- # 16-除了自身以外数组的乘积 ## 题面 > **LeetCode 238. Product of Array Except Self** 给你一个整数数组 `nums`，返回数组 `answer`，其中 `answer[i]` 等于 `nums` 中**除** `nums[i]` **之外其余各元素的乘积**。 题目数据保证数组 `nums` 中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。 请 **不要使用除法**，且在 O(n) 时间复杂度内完成此题。 **示例 1：** ``` 输入：nums = [1, 2, 3, 4] 输出：[24, 12, 8, 6] ``` **示例 2：** ``` 输入：nums = [-1, 1, 0, -3, 3] 输出：[0, 0, 9, 0, 0] ``` **提示：** - `2 <= nums.length <= 10^5` - `-30 <= nums[i] <= 30` - 输入保证 `answer[i]` 在 32 位整数范围内 --- ## 思路 > [!question] 💡 直觉先行：如果允许除法呢？ 如果不看限制条件，最直观的想法很简单——先算出全体乘积 `total`，然后 `answer[i] = total / nums[i]`。 但这里有坑： > [!danger] ⚠️ 为什么这个方法行不通？ > > 1. **除数为零**：如果数组中有 `0`，除法会崩溃。需要额外处理零的个数，逻辑立刻复杂化。 > 2. **题目禁止使用除法**：这本身就是考察点之一。 > > 所以我们需要一个完全不用除法、对零天然免疫的方案。 > [!question] 💡 换个视角：每个位置的答案由什么组成？ 以 `nums = [1, 2, 3, 4]` 为例： ``` answer[0] = 2 × 3 × 4 ← 这是 nums[0] 右边的全部乘积（后缀） answer[1] = 1 × 3 × 4 ← 左边一部分 × 右边一部分 answer[2] = 1 × 2 × 4 ← 左边一部分 × 右边一部分 answer[3] = 1 × 2 × 3 ← 这是 nums[3] 左边的全部乘积（前缀） ``` > [!abstract] 🔑 核心洞察 对于任意位置 `i`： ``` answer[i] = (nums[0] × nums[1] × ... × nums[i-1]) × (nums[i+1] × ... × nums[n-1]) ──────────────── 前缀乘积 ──────────────── ───────── 后缀乘积 ───────── ``` **答案 = 左侧所有数的乘积 × 右侧所有数的乘积。** 所以我们只需要高效地算出每个位置的"左累积"和"右累积"。 ### 方法一：前缀 + 后缀数组（O(n) 空间）⭐ 最直接的想法：预处理两个辅助数组。 > [!abstract] 📐 定义两个辅助数组 - `prefix[i]` = `nums[0] × nums[1] × ... × nums[i-1]`，即 `i` 左边所有元素的乘积。约定 `prefix[0] = 1`（左边没有元素）。 - `suffix[i]` = `nums[i+1] × nums[i+2] × ... × nums[n-1]`，即 `i` 右边所有元素的乘积。约定 `suffix[n-1] = 1`（右边没有元素）。 - `answer[i] = prefix[i] × suffix[i]` > [!step] 算法流程 1. **从左往右扫一遍**，计算每个位置的前缀乘积并填入 `prefix[]` 2. **从右往左扫一遍**，计算每个位置的后缀乘积并填入 `suffix[]` 3. **再扫一遍**，逐位相乘得到答案 用 Mermaid 图表示： ```mermaid flowchart TD Start(["开始"]) --> InitPrefix["初始化前缀数组"] InitPrefix --> Pass1["从左往右扫描
计算 prefix[i]"] Pass1 --> InitSuffix["初始化后缀数组"] InitSuffix --> Pass2["从右往左扫描
计算 suffix[i]"] Pass2 --> Pass3["合并结果
answer[i] = prefix[i] * suffix[i]"] Pass3 --> Return("返回 answer") Return --> End(["结束"]) ``` > [!example] 🔍 逐步跟踪演示 以 `nums = [1, 2, 3, 4]` 为例： **第一遍：从左往右，计算 prefix** | i | nums[i] | 计算 | prefix[i] | |---|---------|------|-----------| | 0 | 1 | 初始化 | 1 | | 1 | 2 | prefix[0] × nums[0] = 1 × 1 | 1 | | 2 | 3 | prefix[1] × nums[1] = 1 × 2 | 2 | | 3 | 4 | prefix[2] × nums[2] = 2 × 3 | 6 | `prefix = [1, 1, 2, 6]` **第二遍：从右往左，计算 suffix** | i | nums[i] | 计算 | suffix[i] | |---|---------|------|-----------| | 3 | 4 | 初始化 | 1 | | 2 | 3 | suffix[3] × nums[3] = 1 × 4 | 4 | | 1 | 2 | suffix[2] × nums[2] = 4 × 3 | 12 | | 0 | 1 | suffix[1] × nums[1] = 12 × 2 | 24 | `suffix = [24, 12, 4, 1]` **第三遍：逐位相乘** | i | prefix[i] | suffix[i] | answer[i] | |---|-----------|-----------|-----------| | 0 | 1 | 24 | **24** | | 1 | 1 | 12 | **12** | | 2 | 2 | 4 | **8** | | 3 | 6 | 1 | **6** | 最终结果：`[24, 12, 8, 6]` ✅ > [!note] 📌 复杂度分析 | 维度 | 复杂度 | 说明 | |------|--------|------| | 时间 | O(n) | 三次线性扫描 | | 空间 | O(n) | 两个辅助数组 `prefix[]` 和 `suffix[]` | 虽然达到了 O(n) 时间，但题目还要求了 **O(1) 额外空间**（输出数组不算），所以需要优化掉这两个辅助数组。 --- ### 方法二：空间优化 —— 复用输出数组（O(1) 额外空间）⭐⭐⭐ > [!question] 💡 关键问题 我们真的需要两个完整的辅助数组吗？仔细观察： - `prefix` 数组在构建完后只被按顺序读取一次 - `suffix` 数组同理，也只用按逆序读一次 这意味着我们可以：**把 `prefix` 直接存进 `answer`，然后用一个变量动态维护 `suffix`**。 > [!abstract] 🔄 核心技巧：用一个变量代替后缀数组 不需要预先分配 `suffix[]`，而是维护一个变量 `R`，表示当前位置**右边**的累积乘积。从右往左遍历时，`R` 依次乘以 `nums[i+1]`，并与 `answer[i]`（里面存的已经是左累积）相乘。 > [!step] 优化后的两步法 1. **第一步（左 → 右）**：在 `answer[]` 中逐个存放"左边所有数的乘积" 2. **第二步（右 → 左）**：用变量 `R` 维护右边累积，依次乘到 `answer[i]` 上 ```mermaid flowchart LR A["初始答案数组"] --> Step1["第一步：从左往右
answer[i] 存左边累积"] Step1 --> B["左累积结果"] B --> Step2["第二步：从右往左
R 维护右边累积并乘入 answer[i]"] Step2 --> C["最终答案"] ``` > [!example] 🔍 逐步跟踪演示 以 `nums = [1, 2, 3, 4]` 为例： **第一步：从左往右，answer[i] 存左累积** | 步骤 | i | R(左累积) | 操作 | answer | |------|---|----------|------|--------| | 初始 | — | — | — | `[_, _, _, _]` | | 1 | 0 | 1 | 初始化 `ans[0]=1`，更新 `R=1×1=1` | `[1, _, _, _]` | | 2 | 1 | 1 | `ans[1]=1`，更新 `R=1×2=2` | `[1, 1, _, _]` | | 3 | 2 | 2 | `ans[2]=2`，更新 `R=2×3=6` | `[1, 1, 2, _]` | | 4 | 3 | 6 | `ans[3]=6`，更新 `R=6×4=24` | `[1, 1, 2, 6]` | 此时 `answer = [1, 1, 2, 6]`，每个位置存的是其左侧所有数的乘积。 **第二步：从右往左，用 R 维护右累积，乘入 answer** | 步骤 | i | 旧 answer[i] | R(右累积) | 操作 | 新 answer[i] | |------|---|-------------|----------|------|-------------| | 初始 | — | `[1,1,2,6]` | 1 | 初始化 | — | | 1 | 3 | 6 | 1 | `ans[3] = 6 × 1 = 6`，更新 `R = 1 × 4 = 4` | `[..., 6]` | | 2 | 2 | 2 | 4 | `ans[2] = 2 × 4 = 8`，更新 `R = 4 × 3 = 12` | `[..., 2, 8, _]` | | 3 | 1 | 1 | 12 | `ans[1] = 1 × 12 = 12`，更新 `R = 12 × 2 = 24` | `[..., 12, _, _]` | | 4 | 0 | 1 | 24 | `ans[0] = 1 × 24 = 24`，更新 `R = 24 × 1 = 24` | `[24, _, _, _]` | 最终结果：`[24, 12, 8, 6]` ✅ > [!quote] 🎯 为什么这个方法成立？ 核心在于 **"左累积已经存在 answer 里，右累积只需边走边算"**： - 正扫时，`answer[i]` 记下了"不看 i，它左边的所有人联手起来的乘积" - 反扫时，`R` 记下了"不看 i，它右边的所有人联手起来的乘积" - 两者相遇的那一刻——就是答案！ 这个过程就像两个人从队伍两端同时出发，各自携带着迎面而来所有人的力量，擦肩而过时交换彼此的力量，就完成了全员"排除自己"的运算。 > [!success] ✅ 空间复杂度证明 - 输出数组 `answer`：不计入额外空间（题目规定） - 变量 `R`：常数级 - 总共：**O(1) 额外空间** ✅ --- > [!example] 🔀 关联变体题 - **LeetCode 3394. Check if Grid can be Cut into Sections** — 同样涉及前缀思想的几何版本 - **LeetCode 238 变体：含零数组** — 当数组可能包含多个 0 时，需要统计 0 的个数来分类讨论 - **LeetCode 2024. Maximize the Confusion of an Exam** — 涉及子数组乘积/计数思维扩展 - **LeetCode 974. Subarray Sums Divisible by K** — 前缀和思想的应用变体（加法而非乘法） --- ## 代码提示 > [!abstract] 📝 Go 伪代码框架（两步法） ```go func productExceptSelf(nums []int) []int { n := len(nums) answer := make([]int, n) // ── 第一步：从左往右，answer[i] 存左累积 ── answer[0] = 1 for i := 1; i < n; i++ { answer[i] = answer[i-1] * nums[i-1] } // ── 第二步：从右往左，R 是右累积 ── R := 1 for i := n - 1; i >= 0; i-- { answer[i] *= R // 左累积 × 右累积 R *= nums[i] // 扩展右累积的范围 } return answer } ``` > [!warning] ⚠️ 注意第二步的顺序 在 `for i := n-1; i >= 0; i--` 循环中，**必须先乘后更新 `R`**： ``` answer[i] *= R ← 这里 R 不含 nums[i]，正确 R *= nums[i] ← 然后才把 nums[i] 纳入 R，为下一轮(i-1)做准备 ``` 如果反过来，`R` 就会多乘一个 `nums[i]`，导致答案错误。 --- ## 技巧 > [!tip] 🔑 核心模式：分离方向的前缀聚合 这道题的技巧核心是 **"将多维依赖降为一维流式计算"**： 1. **拆分问题**：原本每个位置要看其他 n-1 个元素，拆成"只看左边"和"只看右边"两个一维子问题 2. **前置计算**：正向遍历把所有"左贡献"提前算好放进输出数组 3. **在线合并**：反向遍历时用单个变量在线计算"右贡献"，立即与存储的值合并 > [!note] 🐹 Go 中的细节 - `make([]int, n)` 自动将切片元素初始化为 `0`，我们后续会覆盖所有位置，无需手动清零 - Go 的切片迭代支持 `range` 语法，但本题需要**反向遍历**，只能用传统 `for i := n-1; i >= 0; i--` - Go 没有内建的 reverse，手动维护索引变量是最优方案 - 如果遇到全 0 或含多个 0 的特殊测试用例，该方法依然正确（因为完全不涉及除法） > [!success] ✅ 记忆口诀 > 正向铺左累积，逆向乘右累积。 > 一人分饰两角，一步一相逢。 --- ## 代码 ```go // productExceptSelf 返回 answer，其中 answer[i] 等于 nums 中除了 nums[i] // 之外其余各元素的乘积。 // 时间复杂度 O(n)，额外空间 O(1)（输出数组不计入）。 func productExceptSelf(nums []int) []int { n := len(nums) // ── Step 1: 初始化输出数组 ── answer := make([]int, n) // ═══ 第一轮：从左往右，answer[i] 存储 i 左边所有元素的乘积 ═══ // 初始状态：answer[0] 左边没有元素，乘积为 1（单位元） answer[0] = 1 for i := 1; i < n; i++ { // 关键转移：i 的左累积 = (i-1) 的左累积 × nums[i-1] // 因为 ans[i-1] 已经记录了 nums[0..i-2] 的乘积， // 再乘以 nums[i-1] 就得到了 nums[0..i-1] 的乘积 answer[i] = answer[i-1] * nums[i-1] } // 此时 answer 的状态举例（nums = [1,2,3,4]）： // answer = [1, 1, 2, 6] // ↑ ↑ ↑ ↑ // 1 1*1 1*2 1*2*3 // ═══ 第二轮：从右往左，用变量 R 在线维护右边累积 ═══ // R 的含义：从最右侧扩展过来的、不包含当前 i 的乘积 R := 1 // 初始时 ans[n-1] 右边没有元素，R = 1（单位元） for i := n - 1; i >= 0; i-- { // ① 合并：左累积 × 右累积 = 最终答案 answer[i] *= R // ② 扩展：将 nums[i] 纳入 R，供下一个位置（i-1）使用 R *= nums[i] } // 此时 answer 已完整（nums = [1,2,3,4]）： // answer = [24, 12, 8, 6] // 2×3×4 1×3×4 1×2×4 1×2×3 return answer } ``` > [!success] ✅ 运行验证 这是 LeetCode 第 238 题，一道经典的 **"不能用除法的前缀和问题"**。 - **运行时间**：约 5~8 ms（Go，击败 ~95%+ 提交） - **空间消耗**：O(1) 额外空间（输出数组不计入） - **面试表现**：极高。面试官常追问： - 能不能只用一个循环？（不能，信息流向冲突——左累积需要正向，右累积需要反向） - 如果有多个 0 怎么办？（本方法天然免疫，无需特殊处理） - 如果用除法会怎样？（需要先数 0 的个数，至少处理三个分支：0个0/1个0/2个以上0） > [!quote] 💬 延伸思考 "前缀聚合"不仅仅是一种解题技巧，更是一种**降维工具**。当你面对"每个位置都要聚合周围所有其他信息"的问题时，试着问自己： > 这些信息能否按方向拆解？能不能用两次单向遍历替代暴力嵌套？ 这类思维可以迁移到很多场景中，比如字符串匹配中的边界处理、图像滤波中的可分离卷积等。掌握了「正向铺、反向乘」的思路，你就拥有了一套通用的解题模板。