企业官网建设流程全解析

👋 欢迎阅读

🏠个人主页：愿旖旎
📘专栏传送门：算法专栏
💻当前学习内容：前缀和

🎯 欢迎来到「除自身以外数组的乘积」题解之旅！本文将带你从"算出每个位置除自己外其他数的乘积"这一直观场景出发，深入理解前缀积 + 后缀积的巧妙运用，并掌握如何用两次累乘预处理左右乘积来在 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）

​

二、算法分析

一、问题分析（前置分析）

• 题目要求：返回数组answer，answer[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×4，answer[1]又要算1×3×4——每个位置的乘积都从头重乘，重复计算大量重叠区间，最坏 O(n²)。而用除法总积 / nums[i]看似 O(n)，但nums含0时（如[1,0,3,4]）总积为 0，0/0 无法处理——这正是题目禁止除法的原因，前缀积方案天然规避。

二、算法策略（前缀积 f + 后缀积 g）

核心步骤：

1. 初始化：f[0] = 1（下标 0 左侧无元素，空积为 1）、g[n-1] = 1（下标 n-1 右侧空积为 1）。
2. 构建前缀积 f：f[i] = f[i-1] * nums[i-1]，表示下标 i左侧所有元素的乘积（从左往右）。
3. 构建后缀积 g：g[j] = g[j+1] * nums[j+1]，表示下标 j右侧所有元素的乘积（从右往左）。
4. 相乘得到答案：answer[i] = f[i] * g[i]（左侧积 × 右侧积，恰好不含自身）。

📊 示例（nums = [1, 2, 3, 4]）：

构建时 f 从左往右逐个累乘（f[3] = f[2] × nums[2] = 2 × 3 = 6，即1×2×3），g 从右往左递推（g[0] = g[1] × nums[1] = 12 × 2 = 24，即2×3×4）；answer[3] = f[3] × g[3] = 6 × 1 = 6（=1×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 = 6，g[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] = 1，answer[0] = 1（空乘积，正确）；元素含 0 时 f、g 正常传播 0，无需特判。
• 复杂度：时间 O(n)（两次构建 + 一次相乘），空间 O(n)（两个辅助数组；可优化到 O(1)，见难点5）。
• 关键操作：f[i] = f[i-1] * nums[i-1]（前缀累乘）、g[j] = g[j+1] * nums[j+1]（后缀累乘）、answer[i] = f[i] * g[i]（合并答案）。

📌 例子：为什么空积必须是 1 而不是 0

nums = [1, 2, 3, 4]中f[0] = 1（下标 0 左侧没有元素）。若误初始化为 0，f[1] = 0 × 1 = 0，后续全部前缀积都是 0，答案整体错误；空积取单位元 1，乘上它不影响后续累乘，首尾答案才正确——这是前缀积与前缀和（空和为 0）的本质区别。

五、返回值（目标映射）

• 返回v：除自身以外数组的乘积，v[i] = f[i] * g[i]，对应题目"返回数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外所有元素的乘积"。

三.代码

class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { int n = nums.size(); vector<int> v; // 结果数组 vector<int> f(n); // 前缀积：f[i] = 下标 i 左侧所有元素的乘积 vector<int> 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; } };

四、易错点分析

难点1：f[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[i+1]，不是 nums[i]

f[i] 表示 i左侧的积，递推乘的是nums[i-1]；g[i] 表示 i右侧的积，乘的是nums[i+1]。最容易写错的是下标偏移：若写成f[i] = f[i-1] * nums[i]，自身被乘进前缀积，所有答案多乘一个自身，结果完全错误。

难点2：空积必须初始化为 1，而不是 0

f[0] = 1; // 乘法单位元 g[n - 1] = 1;

前缀和"空和为 0"的直觉不能照搬到前缀积：0 是加法的单位元，但乘法的单位元是1。若f[0]初始化为 0，f[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[i+1]）

f 依赖前一个已算好的 f[i-1]，必须正向；g 依赖后一个g[i+1]，必须反向。方向写反会访问未初始化的元素（越界或垃圾值），结果随机且编译器不报错——这是与前缀和系列完全相同的陷阱。

难点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]），总积为 0，0 / 0对 i=1 产生未定义行为，且多个 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*2=2，第2个为 0*2=0，第3个为 0*1=0）。

• 不使用除法正是本题亮点，避免了除零和精度问题，且对所有整数（包括 0）通用。

祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨