LeetCode 238 Product of Array Except Self 题解：四种解法从暴力到 O(1) 空间最优

LeetCode 238 Product of Array Except Self 题解：四种解法从暴力到 O(1) 空间最优

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本篇技术指南以本仓库 articles/products-of-array-discluding-self.md 为骨架，系统讲解 LeetCode 238「除自身以外数组的乘积」的四级递进解法：从 O(n²) 暴力、O(n) 除法、O(n) 空间的前缀/后缀数组，到 O(1) 额外空间的双指针扫描。读完本文，你将掌握前缀积（Prefix Product）与后缀积（Suffix Product）的核心思想，理解零元素处理与整数溢出的边界陷阱，并能对照仓库中 12 种语言的工程实现完成实战验证。

问题回顾与前置知识

给定一个整数数组nums，返回数组answer，其中answer[i]等于nums中除nums[i]之外其余各元素的乘积。

• 输入nums = [1, 2, 3, 4]，输出[24, 12, 8, 6]
• 输入nums = [-1, 1, 0, -3, 3]，输出[0, 0, 9, 0, 0]

在动手之前，需要具备两个基础能力（对应原文档的 Prerequisites 部分）：

• 前缀积/后缀积（Prefix/ Suffix Product）：理解如何从左到右、从右到左分别构建累积乘积，从而避免重复计算。这一思想与本仓库中 products-of-array-discluding-self.md 所强调的方向一致，也是很多数组类题目的通用范式。
• 数组遍历（Array Traversal）：能够通过多趟扫描数组构建中间结果，在空间与时间之间做权衡。

解法一：暴力枚举（Brute Force），O(n²)

直觉

最直观的思路完全照搬题目描述：对每个下标 i，把除它自己以外的所有元素乘起来。这种方法没有任何技巧，但代价是每个位置都要完整扫描一遍数组，整体复杂度为 O(n²)。

算法步骤

1. 设n为输入数组长度，创建大小为n的结果数组res。
2. 对每个下标i（0 到 n-1）：
   • 初始化累积乘积prod = 1。
   • 遍历所有下标j（0 到 n-1），当j != i时执行prod *= nums[j]。
   • 将prod存入res[i]。
3. 返回res。

代码实现

class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) res = [0] * n for i in range(n): prod = 1 for j in range(n): if i == j: continue prod *= nums[j] res[i] = prod return res

class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> res(n); for (int i = 0; i < n; i++) { int prod = 1; for (int j = 0; j < n; j++) { if (i != j) { prod *= nums[j]; } } res[i] = prod; } return res; } };

class Solution { /** * @param {number[]} nums * @return {number[]} */ productExceptSelf(nums) { const n = nums.length; const res = new Array(n); for (let i = 0; i < n; i++) { let prod = 1; for (let j = 0; j < n; j++) { if (i !== j) { prod *= nums[j]; } } res[i] = prod; } return res; } }

func productExceptSelf(nums []int) []int { n := len(nums) res := make([]int, n) for i := 0; i < n; i++ { prod := 1 for j := 0; j < n; j++ { if i == j { continue } prod *= nums[j] } res[i] = prod } return res }

impl Solution { pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> { let n = nums.len(); let mut res = vec![0; n]; for i in 0..n { let mut prod = 1; for j in 0..n { if i != j { prod *= nums[j]; } } res[i] = prod; } res } }

（Java、C#、Kotlin、Swift 版本与原文档一致，实现逻辑完全相同。）

复杂度分析

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$ 额外空间；输出数组占用 $O(n)$。

解法二：除法解法（Division），O(n)

直觉

如果知道所有非零元素的乘积，那么除零问题之外，可以借助除法快速得到每个位置的答案：

• 数组中有两个及以上零：每个位置的乘积必然包含至少一个零 → 整个res全为 0。
• 数组中恰好一个零：只有零所在的位置得到「所有非零元素的乘积」，其余位置全部为 0。
• 数组中没有零：可以直接计算result[i] = total_product // nums[i]。

算法步骤

1. 一趟遍历：
   • 累乘所有非零元素得到prod。
   • 统计零的个数zero_cnt。
2. 若zero_cnt > 1：直接返回全零数组。
3. 创建大小为n的结果数组。
4. 再次遍历：
   • 若存在一个零：零的位置填入prod，其余位置填 0。
   • 若无零：每个位置填入prod // nums[i]。
5. 返回结果数组。

代码实现

class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: prod, zero_cnt = 1, 0 for num in nums: if num: prod *= num else: zero_cnt += 1 if zero_cnt > 1: return [0] * len(nums) res = [0] * len(nums) for i, c in enumerate(nums): if zero_cnt: res[i] = 0 if c else prod else: res[i] = prod // c return res

class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int prod = 1, zeroCount = 0; for (int num : nums) { if (num != 0) { prod *= num; } else { zeroCount++; } } if (zeroCount > 1) { return vector<int>(nums.size(), 0); } vector<int> res(nums.size()); for (size_t i = 0; i < nums.size(); i++) { if (zeroCount > 0) { res[i] = (nums[i] == 0) ? prod : 0; } else { res[i] = prod / nums[i]; } } return res; } };

public class Solution { public int[] productExceptSelf(int[] nums) { int prod = 1, zeroCount = 0; for (int num : nums) { if (num != 0) { prod *= num; } else { zeroCount++; } } if (zeroCount > 1) { return new int[nums.length]; } int[] res = new int[nums.length]; for (int i = 0; i < nums.length; i++) { if (zeroCount > 0) { res[i] = (nums[i] == 0) ? prod : 0; } else { res[i] = prod / nums[i]; } } return res; } }

func productExceptSelf(nums []int) []int { prod := 1 zeroCount := 0 for _, num := range nums { if num != 0 { prod *= num } else { zeroCount++ } } res := make([]int, len(nums)) if zeroCount > 1 { return res } for i, num := range nums { if zeroCount > 0 { if num == 0 { res[i] = prod } else { res[i] = 0 } } else { res[i] = prod / num } } return res }

impl Solution { pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> { let mut prod = 1; let mut zero_count = 0; for &num in &nums { if num != 0 { prod *= num; } else { zero_count += 1; } } if zero_count > 1 { return vec![0; nums.len()]; } let mut res = vec![0; nums.len()]; for (i, &num) in nums.iter().enumerate() { if zero_count > 0 { res[i] = if num == 0 { prod } else { 0 }; } else { res[i] = prod / num; } } res } }

复杂度分析

• 时间复杂度：$O(n)$（两趟线性扫描）
• 空间复杂度：$O(1)$ 额外空间；输出数组占用 $O(n)$。

局限说明

该解法在题目允许使用除法时可行，但 LeetCode 238 原题明确要求不使用除法，且除法在面对零元素时规则复杂。因此它更适合作为思维热身，而非最终提交方案；真正被广泛接受的是下面的前缀/后缀积思路。

解法三：前缀积与后缀积数组（Prefix & Suffix），O(n) 时间 / O(n) 空间

直觉

对每个下标 i，需要的答案是「它左边所有元素的乘积 × 它右边所有元素的乘积」。与其每次重新累乘，不如预先构建两个辅助数组：

• 前缀积数组：pref[i]= 下标 i 左侧所有元素的乘积
• 后缀积数组：suff[i]= 下标 i 右侧所有元素的乘积

于是最终答案就是：

result[i] = pref[i] × suff[i]

因为pref覆盖了 i 之前的所有元素，suff覆盖了 i 之后的所有元素，两者相乘恰好得到「除 nums[i] 以外全部元素的乘积」。

算法步骤

1. 设n为数组长度，创建三个大小为n的数组：pref、suff、res。
2. 初始化边界：
   • pref[0] = 1（下标 0 左侧没有元素）
   • suff[n - 1] = 1（最后一个下标右侧没有元素）
3. 构建前缀积：对i从 1 到 n-1：pref[i] = nums[i - 1] × pref[i - 1]
4. 构建后缀积：对i从 n-2 到 0：suff[i] = nums[i + 1] × suff[i + 1]
5. 合成结果：对每个下标 i：res[i] = pref[i] × suff[i]
6. 返回res。

代码实现

class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: n = len(nums) res = [0] * n pref = [0] * n suff = [0] * n pref[0] = suff[n - 1] = 1 for i in range(1, n): pref[i] = nums[i - 1] * pref[i - 1] for i in range(n - 2, -1, -1): suff[i] = nums[i + 1] * suff[i + 1] for i in range(n): res[i] = pref[i] * suff[i] return res

class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> res(n); vector<int> pref(n); vector<int> suff(n); pref[0] = 1; suff[n - 1] = 1; for (int i = 1; i < n; i++) { pref[i] = nums[i - 1] * pref[i - 1]; } for (int i = n - 2; i >= 0; i--) { suff[i] = nums[i + 1] * suff[i + 1]; } for (int i = 0; i < n; i++) { res[i] = pref[i] * suff[i]; } return res; } };

class Solution { /** * @param {number[]} nums * @return {number[]} */ productExceptSelf(nums) { const n = nums.length; const res = new Array(n); const pref = new Array(n); const suff = new Array(n); pref[0] = 1; suff[n - 1] = 1; for (let i = 1; i < n; i++) { pref[i] = nums[i - 1] * pref[i - 1]; } for (let i = n - 2; i >= 0; i--) { suff[i] = nums[i + 1] * suff[i + 1]; } for (let i = 0; i < n; i++) { res[i] = pref[i] * suff[i]; } return res; } }

func productExceptSelf(nums []int) []int { n := len(nums) res := make([]int, n) pref := make([]int, n) suff := make([]int, n) pref[0], suff[n-1] = 1, 1 for i := 1; i < n; i++ { pref[i] = nums[i-1] * pref[i-1] } for i := n - 2; i >= 0; i-- { suff[i] = nums[i+1] * suff[i+1] } for i := 0; i < n; i++ { res[i] = pref[i] * suff[i] } return res }

impl Solution { pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> { let n = nums.len(); let mut res = vec![0; n]; let mut pref = vec![0; n]; let mut suff = vec![0; n]; pref[0] = 1; suff[n - 1] = 1; for i in 1..n { pref[i] = nums[i - 1] * pref[i - 1]; } for i in (0..n - 1).rev() { suff[i] = nums[i + 1] * suff[i + 1]; } for i in 0..n { res[i] = pref[i] * suff[i]; } res } }

复杂度分析

• 时间复杂度：$O(n)$（三趟线性扫描）
• 空间复杂度：$O(n)$（pref与suff两个辅助数组，外加输出数组）

解法四：前缀后缀空间优化（Optimal），O(n) 时间 / O(1) 额外空间

直觉

能否不用额外的前缀/后缀数组？可以——直接复用输出数组res作为前缀积的载体，再用一个滚动变量累计后缀积：

• 第一趟（从左到右）：把res[i]填成 i 左侧所有元素的乘积（前缀积）。
• 第二趟（从右到左）：用一个postfix变量累计右侧乘积，逐位乘回res[i]。

这样既保留了解法三的完整逻辑，又把额外空间压到 O(1)（输出数组不计入额外空间）。

算法步骤

1. 初始化结果数组res，全部填 1。
2. 创建变量prefix = 1。
3. 第一趟（左到右）：
   • 对每个下标 i：令res[i] = prefix（左侧乘积），随后prefix *= nums[i]。
4. 创建变量postfix = 1。
5. 第二趟（右到左）：
   • 对每个下标 i：令res[i] *= postfix（乘上右侧乘积），随后postfix *= nums[i]。
6. 返回res。

代码实现

class Solution: def productExceptSelf(self, nums: List[int]) -> List[int]: res = [1] * (len(nums)) prefix = 1 for i in range(len(nums)): res[i] = prefix prefix *= nums[i] postfix = 1 for i in range(len(nums) - 1, -1, -1): res[i] *= postfix postfix *= nums[i] return res

class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> res(n, 1); for (int i = 1; i < n; i++) { res[i] = res[i - 1] * nums[i - 1]; } int postfix = 1; for (int i = n - 1; i >= 0; i--) { res[i] *= postfix; postfix *= nums[i]; } return res; } };

public class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] res = new int[n]; res[0] = 1; for (int i = 1; i < n; i++) { res[i] = res[i - 1] * nums[i - 1]; } int postfix = 1; for (int i = n - 1; i >= 0; i--) { res[i] *= postfix; postfix *= nums[i]; } return res; } }

class Solution { /** * @param {number[]} nums * @return {number[]} */ productExceptSelf(nums) { const n = nums.length; const res = new Array(n).fill(1); for (let i = 1; i < n; i++) { res[i] = res[i - 1] * nums[i - 1]; } let postfix = 1; for (let i = n - 1; i >= 0; i--) { res[i] *= postfix; postfix *= nums[i]; } return res; } }

func productExceptSelf(nums []int) []int { res := make([]int, len(nums)) for i := range res { res[i] = 1 } prefix := 1 for i := 0; i < len(nums); i++ { res[i] = prefix prefix *= nums[i] } postfix := 1 for i := len(nums) - 1; i >= 0; i-- { res[i] *= postfix postfix *= nums[i] } return res }

impl Solution { pub fn product_except_self(nums: Vec<i32>) -> Vec<i32> { let n = nums.len(); let mut res = vec![1; n]; let mut prefix = 1; for i in 0..n { res[i] = prefix; prefix *= nums[i]; } let mut postfix = 1; for i in (0..n).rev() { res[i] *= postfix; postfix *= nums[i]; } res } }

复杂度分析

• 时间复杂度：$O(n)$（两趟线性扫描）
• 空间复杂度：$O(1)$ 额外空间；输出数组占用 $O(n)$。

仓库源码印证：多语言工程实现

本仓库为 LeetCode 238 提供了完整的 12 语言工程实现，均采用解法四（O(1) 额外空间）的写法，可以直接对照验证：

• Python：python/0238-product-of-array-except-self.py —— 先正向用res[i] = res[i-1] * nums[i-1]构建前缀积，再反向乘后缀积，与本文解法四完全一致。
• C++：cpp/0238-product-of-array-except-self.cpp —— 文件头注释明确记录了题目示例（[1,2,3,4] -> [24,12,8,6]、[-1,1,0,-3,3] -> [0,0,9,0,0]）以及「先正向算前缀积、第二趟反向算后缀积」的策略，并标注 Time O(n)、Space O(1)。
• C：c/0238-product-of-array-except-self.c —— 需要手动malloc并设置*returnSize = numsSize，注释明确说明返回数组必须由调用方free，这是 C 语言实现与高层语言在内存管理上的关键差异。
• Java：java/0238-product-of-array-except-self.java —— 注释点明「第一趟算除自身外的左积，第二趟算右积」；同一文件还附带了productExceptSelfNumsAsPrefix变体：直接在输入数组上滚动维护后缀积，进一步把辅助变量降到最少。
• Go：go/0238-product-of-array-except-self.go、JavaScript：javascript/0238-product-of-array-except-self.js、TypeScript：typescript/0238-product-of-array-except-self.ts 均采用prefix/postfix双滚动变量写法。
• Rust：rust/0238-product-of-array-except-self.rs 通过res.iter_mut().enumerate().rev()反向迭代原地修改，体现了 Rust 的所有权与迭代器风格。
• 其余语言（C#、Kotlin、Ruby、Swift）分别位于 csharp/0238-product-of-array-except-self.cs、kotlin/0238-product-of-array-except-self.kt、ruby/0238-product-of-array-except-self.rb、swift/0238-product-of-array-except-self.swift。

从源码结构可以推断，本仓库的惯例是：每个题目一个文件、以题目编号（0238）命名、统一使用Solution类/productExceptSelf函数签名，方便跨语言对照学习与在线评测直接提交。

常见陷阱（Common Pitfalls）

陷阱一：用除法却不处理零

totalProduct / nums[i]的写法在数组包含 0 时会直接失败：除以 0 引发运行时错误，多个零的情况更是需要特殊分支。正确做法是先统计零的个数：

• 零的个数 ≥ 2：整个结果全为 0；
• 零的个数 = 1：只有零所在位置得到「非零元素乘积」，其余位置为 0；
• 零的个数 = 0：才能安全执行total / nums[i]。

本文解法二正是基于这一分类讨论实现的。

陷阱二：前缀/后缀数组构建中的边界错误（Off-by-One）

构建前缀积时，pref[i]应存放下标 i 之前所有元素的乘积，绝不能包含nums[i]本身，否则该元素会被重复计入，导致结果错误。后缀数组同理：suff[i]必须排除nums[i]。这也是为什么边界必须初始化为pref[0] = 1、suff[n-1] = 1（空乘积恒为 1），而不是nums[0]或nums[n-1]。

陷阱三：大乘积的整数溢出

当数组中包含很多大数时，乘积可能超出 32 位整数的表示范围。在定长整数语言（如 C、C++、Java 的int）中，应视情况改用long或BigInteger。题目约束通常设计为不会溢出，但针对「多个元素接近最大值」的边界用例仍需自测验证。这也解释了为何仓库的 C 实现在 c/0238-product-of-array-except-self.c 中直接以int返回——其前提是评测数据规模在 32 位范围内。

小结：四种解法的取舍

LeetCode 238 原题要求不使用除法，因此解法四是本题的推荐提交方案：两趟扫描、O(1) 额外空间，同时天然规避了零元素与除法带来的所有边界问题。掌握前缀积/后缀积这一思想后，还可以迁移到「子数组乘积」「前缀和统计」等一系列数组累积类问题上（本仓库的 products-of-array-discluding-self.md 同样将其列为前置知识）。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode