366 lines
13 KiB
Markdown
366 lines
13 KiB
Markdown
---
|
||
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["从左往右扫描<br/>计算 prefix[i]"]
|
||
Pass1 --> InitSuffix["初始化后缀数组"]
|
||
InitSuffix --> Pass2["从右往左扫描<br/>计算 suffix[i]"]
|
||
Pass2 --> Pass3["合并结果<br/>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["第一步：从左往右<br/>answer[i] 存左边累积"]
|
||
Step1 --> B["左累积结果"]
|
||
B --> Step2["第二步：从右往左<br/>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] 💬 延伸思考
|
||
|
||
"前缀聚合"不仅仅是一种解题技巧，更是一种**降维工具**。当你面对"每个位置都要聚合周围所有其他信息"的问题时，试着问自己：
|
||
|
||
> 这些信息能否按方向拆解？能不能用两次单向遍历替代暴力嵌套？
|
||
|
||
这类思维可以迁移到很多场景中，比如字符串匹配中的边界处理、图像滤波中的可分离卷积等。掌握了「正向铺、反向乘」的思路，你就拥有了一套通用的解题模板。
|