leetcode-go/普通数组/16-除了自身以外数组的乘积.md

tags, create time

tags	create time
LeetCode 前缀和 数组 中等	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 图表示：

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] 上

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 伪代码框架（两步法）

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] ✅ 记忆口诀

正向铺左累积，逆向乘右累积。
一人分饰两角，一步一相逢。

---

代码

// 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] 💬 延伸思考

"前缀聚合"不仅仅是一种解题技巧，更是一种降维工具。当你面对"每个位置都要聚合周围所有其他信息"的问题时，试着问自己：

这些信息能否按方向拆解？能不能用两次单向遍历替代暴力嵌套？

这类思维可以迁移到很多场景中，比如字符串匹配中的边界处理、图像滤波中的可分离卷积等。掌握了「正向铺、反向乘」的思路，你就拥有了一套通用的解题模板。