欢迎阅读个人主页愿旖旎专栏传送门算法专栏当前学习内容前缀和 欢迎来到「除自身以外数组的乘积」题解之旅本文将带你从算出每个位置除自己外其他数的乘积这一直观场景出发深入理解前缀积 后缀积的巧妙运用并掌握如何用两次累乘预处理左右乘积来在 O(n) 内得到全部答案。在开始之前建议你先了解题目背景这是 LeetCode 238 题给定整数数组nums返回数组answer其中answer[i]等于nums中除nums[i]之外所有元素的乘积且不允许使用除法。本质上每个答案 左侧所有数的乘积 × 右侧所有数的乘积问题转化为预处理前缀积与后缀积再相乘。明确学习目标掌握前缀积 f 与后缀积 g 的构建理解f[i]、g[i] 均不含 nums[i] 本身的语义与空积初始化为 1并熟练处理含 0 元素与单元素数组等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [1,2,3,4]输出[24,12,8,6]。本文将从问题转化、左右累乘、双积相乘、边界防护到代码实现层层递进。即使你对前缀积还不熟悉我们也会从左边的积乘上右边的积就是除自己外的积这一直觉出发让你轻松抓住核心思想——左积右积相乘即答。现在让我们一起累乘左右两侧算出每个位置的乘积吧 ✖️一.题目238. 除了自身以外数组的乘积 - 力扣LeetCode​二、算法分析一、问题分析前置分析题目要求返回数组answeranswer[i]nums中除nums[i]外所有元素的乘积禁止使用除法。关键约束不能用除法元素可能为0除法会失效本解法天然规避要求 O(n) 时间。核心思路暴力做法对每个位置都重新乘一遍其他元素总代价 O(n²)用前缀积 f左侧乘积与后缀积 g右侧乘积各预处理一遍answer[i] f[i] * g[i]总复杂度O(n)。 例子暴力为什么不可行且除法为何不能用数组[1, 2, 3, 4]answer[0]需算2×3×4answer[1]又要算1×3×4——每个位置的乘积都从头重乘重复计算大量重叠区间最坏 O(n²)。而用除法总积 / nums[i]看似 O(n)但nums含0时如[1,0,3,4]总积为 00/0 无法处理——这正是题目禁止除法的原因前缀积方案天然规避。二、算法策略前缀积 f 后缀积 g核心步骤初始化f[0] 1下标 0 左侧无元素空积为 1、g[n-1] 1下标 n-1 右侧空积为 1。构建前缀积 ff[i] f[i-1] * nums[i-1]表示下标 i左侧所有元素的乘积从左往右。构建后缀积 gg[j] g[j1] * nums[j1]表示下标 j右侧所有元素的乘积从右往左。相乘得到答案answer[i] f[i] * g[i]左侧积 × 右侧积恰好不含自身。 示例nums [1, 2, 3, 4]下标 i0123nums[i]1234f[i]左侧积1126g[i]右侧积241241answer[i] f[i]×g[i]241286构建时 f 从左往右逐个累乘f[3] f[2] × nums[2] 2 × 3 6即1×2×3g 从右往左递推g[0] g[1] × nums[1] 12 × 2 24即2×3×4answer[3] f[3] × g[3] 6 × 1 61×2×3每个答案恰好是除自身外全部元素的积。三、正确性说明简单版本f、g 语义精确f[i] nums[0] × ... × nums[i-1]递推保证恰好是 i 左侧全部元素的乘积不含 nums[i]g[i]对称地是右侧全部元素的乘积递推无误差。相乘条件等价answer[i] f[i] × g[i] 左侧积 × 右侧积 除 nums[i] 外所有元素的乘积与题目定义逐字对应不会算错。空积单位元正确f[0] 1、g[n-1] 1使空侧的乘积等于乘法单位元 1乘上 1 不影响结果首尾位置也能正确得到答案。含 0 时仍成立乘法中 0 的传播是精确的f、g 中 0 出现的位置由实际乘积决定不依赖除法任何含 0 的输入都正确。 例子为什么 f[i] 不含 nums[i] 本身下标 3 处f[3] 1 × 2 × 3 6g[3] 1空积answer[3] 6 × 1 6——nums[3] 4没有参与任何一侧的乘积若误把自身乘进去如f[3]写成1×2×3×4答案会多乘一个 4全部错位。四、实现细节边界防护初始化f、g均开n大小f[0] 1、g[n-1] 1乘法单位元不是 0。边界防护构建 f 时i从 1 到n-1构建 g 时j从n-2到 0均不越界n 1时f[0] g[0] 1answer[0] 1空乘积正确元素含 0 时 f、g 正常传播 0无需特判。复杂度时间 O(n)两次构建 一次相乘空间 O(n)两个辅助数组可优化到 O(1)见难点5。关键操作f[i] f[i-1] * nums[i-1]前缀累乘、g[j] g[j1] * nums[j1]后缀累乘、answer[i] f[i] * g[i]合并答案。 例子为什么空积必须是 1 而不是 0nums [1, 2, 3, 4]中f[0] 1下标 0 左侧没有元素。若误初始化为 0f[1] 0 × 1 0后续全部前缀积都是 0答案整体错误空积取单位元 1乘上它不影响后续累乘首尾答案才正确——这是前缀积与前缀和空和为 0的本质区别。五、返回值目标映射返回v除自身以外数组的乘积v[i] f[i] * g[i]对应题目返回数组 answer其中 answer[i] 等于 nums 中除 nums[i] 之外所有元素的乘积。三.代码class Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint v; // 结果数组 vectorint f(n); // 前缀积f[i] 下标 i 左侧所有元素的乘积 vectorint g(n); // 后缀积g[i] 下标 i 右侧所有元素的乘积 f[0] 1; // 空积左侧无元素乘积为单位元 1 g[n - 1] 1; // 空积右侧无元素乘积为单位元 1 // 1. 构建前缀积 f从左往右累乘不含 nums[i] 自身 for (int i 1; i n; i) { f[i] f[i - 1] * nums[i - 1]; } // 2. 构建后缀积 g从右往左累乘不含 nums[j] 自身 for (int i n - 2; i 0; i--) { g[i] g[i 1] * nums[i 1]; } // 3. 合并答案左侧积 × 右侧积 除自身外全部元素的乘积 for (int i 0; i n; i) { v.push_back(f[i] * g[i]); } return v; } };四、易错点分析难点1f[i]、g[i] 的语义——不含 nums[i] 本身f[i] f[i - 1] * nums[i - 1]; // 乘的是 nums[i-1]不是 nums[i] g[i] g[i 1] * nums[i 1]; // 乘的是 nums[i1]不是 nums[i]f[i] 表示 i左侧的积递推乘的是nums[i-1]g[i] 表示 i右侧的积乘的是nums[i1]。最容易写错的是下标偏移若写成f[i] f[i-1] * nums[i]自身被乘进前缀积所有答案多乘一个自身结果完全错误。难点2空积必须初始化为 1而不是 0f[0] 1; // 乘法单位元 g[n - 1] 1;前缀和空和为 0的直觉不能照搬到前缀积0 是加法的单位元但乘法的单位元是1。若f[0]初始化为 0f[1] 0 × nums[0] 0所有前缀积全部变成 0答案整体错误。单位元选错是前缀积最隐蔽的错误且编译器不会报错。难点3两个数组的构建方向相反for (int i 1; i n; i) // f从左往右依赖 f[i-1] for (int i n - 2; i 0; i--) // g从右往左依赖 g[i1]f 依赖前一个已算好的 f[i-1]必须正向g 依赖后一个g[i1]必须反向。方向写反会访问未初始化的元素越界或垃圾值结果随机且编译器不报错——这是与前缀和系列完全相同的陷阱。难点4为什么不能直接用除法// 错误示范answer[i] 总积 / nums[i] int total 1; for (int x : nums) total * x; for (int i 0; i n; i) answer[i] total / nums[i];除法看似 O(n) 简洁但有两个致命问题① 题目明确禁止使用除法②nums含0时如[1,0,3,4]总积为 00 / 0对 i1 产生未定义行为且多个 0 时除法逻辑彻底失效。前缀积方案不依赖除法天然规避 0 问题。五、流程图 闭幕 恭喜你完成了「除自身以外数组的乘积」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题使用前缀积f[i]和后缀积g[i]分别记录每个位置左侧和右侧所有元素的乘积。为什么f[0] 1和g[n-1] 1这里的单位元 1 在乘法运算中起到什么作用构建f数组时f[i] f[i-1] * nums[i-1]为什么左侧积不包含nums[i]自身如果包含自身最终的答案公式应如何调整本题使用了两个辅助数组空间复杂度 O(n)。能否只用一个结果数组ans和两个变量或者一个变量来实现 O(1) 额外空间请简述思路。如果数组中存在0当前算法是否仍然正确请举例说明如nums [0, 1, 2]。如果题目要求返回结果数组的同时不能使用除法运算当前方法满足要求吗相比使用除法这种方法有什么优势点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案f[0]1和g[n-1]1表示空积没有元素时的乘积在乘法中单位元为 1这样即使中心下标在端点左侧或右侧为空时乘积仍为 1与其他位置的乘积能正确相乘。不包含自身是为了直接计算“除自身外”的乘积若包含自身则最终答案需除以nums[i]但这会引入除法且无法处理 0。可优化为 O(1) 额外空间先用ans数组存储左侧积再从右向左扫描用变量rightProd累乘右侧元素同时ans[i] * rightProd最后返回ans无需额外数组。含 0 时依然正确例如[0,1,2]f[1,0,0]g[2,2,1]结果[2,0,0]符合“除自身外乘积”第1个为 1*22第2个为 0*20第3个为 0*10。不使用除法正是本题亮点避免了除零和精度问题且对所有整数包括 0通用。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨