 空间最优)
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 ForceO(n²)直觉最直观的思路完全照搬题目描述对每个下标 i把除它自己以外的所有元素乘起来。这种方法没有任何技巧但代价是每个位置都要完整扫描一遍数组整体复杂度为 O(n²)。算法步骤设n为输入数组长度创建大小为n的结果数组res。对每个下标i0 到 n-1初始化累积乘积prod 1。遍历所有下标j0 到 n-1当j ! i时执行prod * nums[j]。将prod存入res[i]。返回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 resclass Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint 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: Veci32) - Veci32 { 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)$。解法二除法解法DivisionO(n)直觉如果知道所有非零元素的乘积那么除零问题之外可以借助除法快速得到每个位置的答案数组中有两个及以上零每个位置的乘积必然包含至少一个零 → 整个res全为 0。数组中恰好一个零只有零所在的位置得到「所有非零元素的乘积」其余位置全部为 0。数组中没有零可以直接计算result[i] total_product // nums[i]。算法步骤一趟遍历累乘所有非零元素得到prod。统计零的个数zero_cnt。若zero_cnt 1直接返回全零数组。创建大小为n的结果数组。再次遍历若存在一个零零的位置填入prod其余位置填 0。若无零每个位置填入prod // nums[i]。返回结果数组。代码实现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 resclass Solution { public: vectorint productExceptSelf(vectorint nums) { int prod 1, zeroCount 0; for (int num : nums) { if (num ! 0) { prod * num; } else { zeroCount; } } if (zeroCount 1) { return vectorint(nums.size(), 0); } vectorint 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: Veci32) - Veci32 { 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 SuffixO(n) 时间 / O(n) 空间直觉对每个下标 i需要的答案是「它左边所有元素的乘积 × 它右边所有元素的乘积」。与其每次重新累乘不如预先构建两个辅助数组前缀积数组pref[i] 下标 i 左侧所有元素的乘积后缀积数组suff[i] 下标 i 右侧所有元素的乘积于是最终答案就是result[i] pref[i] × suff[i]因为pref覆盖了 i 之前的所有元素suff覆盖了 i 之后的所有元素两者相乘恰好得到「除 nums[i] 以外全部元素的乘积」。算法步骤设n为数组长度创建三个大小为n的数组pref、suff、res。初始化边界pref[0] 1下标 0 左侧没有元素suff[n - 1] 1最后一个下标右侧没有元素构建前缀积对i从 1 到 n-1pref[i] nums[i - 1] × pref[i - 1]构建后缀积对i从 n-2 到 0suff[i] nums[i 1] × suff[i 1]合成结果对每个下标 ires[i] pref[i] × suff[i]返回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 resclass Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint res(n); vectorint pref(n); vectorint 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[i1] * suff[i1] } for i : 0; i n; i { res[i] pref[i] * suff[i] } return res }impl Solution { pub fn product_except_self(nums: Veci32) - Veci32 { 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两个辅助数组外加输出数组解法四前缀后缀空间优化OptimalO(n) 时间 / O(1) 额外空间直觉能否不用额外的前缀/后缀数组可以——直接复用输出数组res作为前缀积的载体再用一个滚动变量累计后缀积第一趟从左到右把res[i]填成 i 左侧所有元素的乘积前缀积。第二趟从右到左用一个postfix变量累计右侧乘积逐位乘回res[i]。这样既保留了解法三的完整逻辑又把额外空间压到 O(1)输出数组不计入额外空间。算法步骤初始化结果数组res全部填 1。创建变量prefix 1。第一趟左到右对每个下标 i令res[i] prefix左侧乘积随后prefix * nums[i]。创建变量postfix 1。第二趟右到左对每个下标 i令res[i] * postfix乘上右侧乘积随后postfix * nums[i]。返回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 resclass Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint 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: Veci32) - Veci32 { 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) 额外空间的写法可以直接对照验证Pythonpython/0238-product-of-array-except-self.py —— 先正向用res[i] res[i-1] * nums[i-1]构建前缀积再反向乘后缀积与本文解法四完全一致。Ccpp/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)。Cc/0238-product-of-array-except-self.c —— 需要手动malloc并设置*returnSize numsSize注释明确说明返回数组必须由调用方free这是 C 语言实现与高层语言在内存管理上的关键差异。Javajava/0238-product-of-array-except-self.java —— 注释点明「第一趟算除自身外的左积第二趟算右积」同一文件还附带了productExceptSelfNumsAsPrefix变体直接在输入数组上滚动维护后缀积进一步把辅助变量降到最少。Gogo/0238-product-of-array-except-self.go、JavaScriptjavascript/0238-product-of-array-except-self.js、TypeScripttypescript/0238-product-of-array-except-self.ts 均采用prefix/postfix双滚动变量写法。Rustrust/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 位范围内。小结四种解法的取舍解法时间复杂度额外空间是否使用除法适用场景暴力枚举$O(n^2)$$O(1)$否仅用于理解题意除法$O(n)$$O(1)$是允许除法且零元素可分类讨论时前缀/后缀数组$O(n)$$O(n)$否空间充裕、注重可读性前缀/后缀优化$O(n)$$O(1)$否面试与竞赛的标准答案LeetCode 238 原题要求不使用除法因此解法四是本题的推荐提交方案两趟扫描、O(1) 额外空间同时天然规避了零元素与除法带来的所有边界问题。掌握前缀积/后缀积这一思想后还可以迁移到「子数组乘积」「前缀和统计」等一系列数组累积类问题上本仓库的 products-of-array-discluding-self.md 同样将其列为前置知识。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 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 ForceO(n²)直觉最直观的思路完全照搬题目描述对每个下标 i把除它自己以外的所有元素乘起来。这种方法没有任何技巧但代价是每个位置都要完整扫描一遍数组整体复杂度为 O(n²)。算法步骤设n为输入数组长度创建大小为n的结果数组res。对每个下标i0 到 n-1初始化累积乘积prod 1。遍历所有下标j0 到 n-1当j ! i时执行prod * nums[j]。将prod存入res[i]。返回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 resclass Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint 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: Veci32) - Veci32 { 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)$。解法二除法解法DivisionO(n)直觉如果知道所有非零元素的乘积那么除零问题之外可以借助除法快速得到每个位置的答案数组中有两个及以上零每个位置的乘积必然包含至少一个零 → 整个res全为 0。数组中恰好一个零只有零所在的位置得到「所有非零元素的乘积」其余位置全部为 0。数组中没有零可以直接计算result[i] total_product // nums[i]。算法步骤一趟遍历累乘所有非零元素得到prod。统计零的个数zero_cnt。若zero_cnt 1直接返回全零数组。创建大小为n的结果数组。再次遍历若存在一个零零的位置填入prod其余位置填 0。若无零每个位置填入prod // nums[i]。返回结果数组。代码实现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 resclass Solution { public: vectorint productExceptSelf(vectorint nums) { int prod 1, zeroCount 0; for (int num : nums) { if (num ! 0) { prod * num; } else { zeroCount; } } if (zeroCount 1) { return vectorint(nums.size(), 0); } vectorint 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: Veci32) - Veci32 { 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 SuffixO(n) 时间 / O(n) 空间直觉对每个下标 i需要的答案是「它左边所有元素的乘积 × 它右边所有元素的乘积」。与其每次重新累乘不如预先构建两个辅助数组前缀积数组pref[i] 下标 i 左侧所有元素的乘积后缀积数组suff[i] 下标 i 右侧所有元素的乘积于是最终答案就是result[i] pref[i] × suff[i]因为pref覆盖了 i 之前的所有元素suff覆盖了 i 之后的所有元素两者相乘恰好得到「除 nums[i] 以外全部元素的乘积」。算法步骤设n为数组长度创建三个大小为n的数组pref、suff、res。初始化边界pref[0] 1下标 0 左侧没有元素suff[n - 1] 1最后一个下标右侧没有元素构建前缀积对i从 1 到 n-1pref[i] nums[i - 1] × pref[i - 1]构建后缀积对i从 n-2 到 0suff[i] nums[i 1] × suff[i 1]合成结果对每个下标 ires[i] pref[i] × suff[i]返回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 resclass Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint res(n); vectorint pref(n); vectorint 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[i1] * suff[i1] } for i : 0; i n; i { res[i] pref[i] * suff[i] } return res }impl Solution { pub fn product_except_self(nums: Veci32) - Veci32 { 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两个辅助数组外加输出数组解法四前缀后缀空间优化OptimalO(n) 时间 / O(1) 额外空间直觉能否不用额外的前缀/后缀数组可以——直接复用输出数组res作为前缀积的载体再用一个滚动变量累计后缀积第一趟从左到右把res[i]填成 i 左侧所有元素的乘积前缀积。第二趟从右到左用一个postfix变量累计右侧乘积逐位乘回res[i]。这样既保留了解法三的完整逻辑又把额外空间压到 O(1)输出数组不计入额外空间。算法步骤初始化结果数组res全部填 1。创建变量prefix 1。第一趟左到右对每个下标 i令res[i] prefix左侧乘积随后prefix * nums[i]。创建变量postfix 1。第二趟右到左对每个下标 i令res[i] * postfix乘上右侧乘积随后postfix * nums[i]。返回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 resclass Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint 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: Veci32) - Veci32 { 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) 额外空间的写法可以直接对照验证Pythonpython/0238-product-of-array-except-self.py —— 先正向用res[i] res[i-1] * nums[i-1]构建前缀积再反向乘后缀积与本文解法四完全一致。Ccpp/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)。Cc/0238-product-of-array-except-self.c —— 需要手动malloc并设置*returnSize numsSize注释明确说明返回数组必须由调用方free这是 C 语言实现与高层语言在内存管理上的关键差异。Javajava/0238-product-of-array-except-self.java —— 注释点明「第一趟算除自身外的左积第二趟算右积」同一文件还附带了productExceptSelfNumsAsPrefix变体直接在输入数组上滚动维护后缀积进一步把辅助变量降到最少。Gogo/0238-product-of-array-except-self.go、JavaScriptjavascript/0238-product-of-array-except-self.js、TypeScripttypescript/0238-product-of-array-except-self.ts 均采用prefix/postfix双滚动变量写法。Rustrust/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 位范围内。小结四种解法的取舍解法时间复杂度额外空间是否使用除法适用场景暴力枚举$O(n^2)$$O(1)$否仅用于理解题意除法$O(n)$$O(1)$是允许除法且零元素可分类讨论时前缀/后缀数组$O(n)$$O(n)$否空间充裕、注重可读性前缀/后缀优化$O(n)$$O(1)$否面试与竞赛的标准答案LeetCode 238 原题要求不使用除法因此解法四是本题的推荐提交方案两趟扫描、O(1) 额外空间同时天然规避了零元素与除法带来的所有边界问题。掌握前缀积/后缀积这一思想后还可以迁移到「子数组乘积」「前缀和统计」等一系列数组累积类问题上本仓库的 products-of-array-discluding-self.md 同样将其列为前置知识。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考