C++ 前缀积 高频笔试考点 实用技巧 力扣 238.除自身以外数组的乘积 题解 每日一题

题目解析

题目链接：力扣 238. 除自身以外数组的乘积

题目描述：

示例 1：
输入：nums = [1,2,3,4]
输出：[24,12,8,6]
解释：
answer[0] = 2×3×4 = 24
answer[1] = 1×3×4 = 12
answer[2] = 1×2×4 = 8
answer[3] = 1×2×3 = 6

示例 2：
输入：nums = [-1,1,0,-3,3]
输出：[0,0,9,0,0]
解释：
因 nums[2] = 0，除 nums[2] 外其他元素乘积均包含 0，故 answer[0]、answer[1]、answer[3]、answer[4] 为 0；
answer[2] = (-1)×1×(-3)×3 = 9。

提示：
2 <= nums.length <= 10⁵
-30 <= nums[i] <= 30
保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数 范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

为什么这道题值得深入学习？

这道题是 “前缀积/后缀积” 思想的经典进阶题，核心价值远超“计算乘积”本身：

1. 规避“除法陷阱”：若用“总乘积÷当前元素”的思路，会遇到“数组含0”（除法无意义）和“精度丢失”（整数除法截断）的问题，强迫我们跳出惯性思维；
2. 强化“预计算”优化逻辑：延续“前缀和”减少重复计算的核心，但从“求和”拓展到“求积”，进一步理解“预存区间结果”在不同场景的应用；
3. 空间优化的关键练习：基础解法用两个辅助数组（前缀积+后缀积），进阶要求将空间压到 O(1)，能锻炼“复用数组、减少冗余存储”的思维，为复杂算法（如动态规划空间优化）铺垫；
4. 衔接高频考点：本题的“前缀积+后缀积”思路可迁移到“二维矩阵除自身外乘积”“子数组乘积小于k”等题目，是数组类问题的核心解题模板之一。

常见误区：为什么不能用“总乘积÷当前元素”？

很多人第一反应是“先算所有元素的总乘积，再逐个除以每个元素”，但这种思路存在两个致命问题，完全不符合题目要求：

1. 数组含0时失效：若 nums 中有一个0，总乘积为0，此时除以非0元素结果为0（正确），但除以0会触发数学错误（无法计算）；若有两个及以上0，所有 answer[i] 均为0，但“总乘积÷0”仍无法处理；
2. 违反进阶要求：题目明确暗示“不要使用除法”，且即使忽略这点，除法的时间复杂度虽为 O(n)，但无法应对“禁止除法”的场景（如后续扩展到模运算环境，除法无逆元）。

因此，必须放弃除法思路，转向“预计算前后区间乘积”的正确方向。/(ㄒoㄒ)/~~

为什么能用“前缀积+后缀积”？

本题的核心需求是：对每个下标 i，计算 “左侧所有元素的乘积” × “右侧所有元素的乘积”。这与“寻找中心下标”中“左侧和+右侧和”的逻辑高度相似，但从“和”变为“积”，且需要将两者相乘。

“前缀积+后缀积”的适用场景与前缀和一致，且完美契合本题：

1. 多次查询区间积：对每个 i 需查询“左侧区间积”和“右侧区间积”，共 2n 次查询，预计算后可将每次查询从 O(n) 降至 O(1)；
2. 数组静态无修改：nums 是给定的静态数组，无动态插入/删除/更新，前缀积和后缀积计算一次后可反复使用；
3. 乘积无溢出风险：题目明确保证“任意元素的全部前缀和后缀乘积都在32位整数范围内”，无需处理溢出问题，可放心计算。

核心思路：前缀积+后缀积的原理

前缀积数组的确定
我们需要两个辅助数组，分别存储“左侧区间积”和“右侧区间积”：

• 前缀积数组 f：f[i] 表示 nums[0] ~ nums[i-1] 的乘积（即 i 左侧所有元素的乘积，不包含 i 本身）；

• 后缀积数组 g：g[i] 表示 nums[i+1] ~ nums[n-1] 的乘积（即 i 右侧所有元素的乘积，不包含 i 本身）。

此时，answer[i] = f[i] × g[i]，因为“除 nums[i] 外所有元素的乘积”=“左侧积”ד右侧积”。

预计算过程：如何推导递推公式？
前缀积 f 和后缀积 g 的递推公式不是凭空而来，而是基于“区间连续性”推导，关键是找到相邻下标的乘积关系：👇

1. 前缀积数组 f 的计算（从左往右）
目标：f[i] 是 0 ~ i-1 的积，观察相邻下标的关系：

• 当 i=0 时：i 左侧无元素，乘积为 1（乘法的单位元，类似加法的0，乘1不改变结果），故 f[0] = 1；
  

• 当 i=1 时：f[1] 是 0 ~ 0 的积（即 nums[0]），而 f[0] = 1，因此 f[1] = f[0] × nums[0]；

• 当 i=2 时：f[2] 是 0 ~ 1 的积（即 nums[0]×nums[1]），而 f[1] = nums[0]，因此 f[2] = f[1] × nums[1]；

• 以此类推，对 i ≥ 1：f[i] 的区间（0 ~ i-1）= f[i-1] 的区间（0 ~ i-2）× 新增元素 nums[i-1]。

最终递推公式：f[i] = f[i-1] × nums[i-1]（i 从 1 到 n-1）。

2. 后缀积数组 g 的计算（从右往左）
目标：g[i] 是 i+1 ~ n-1 的积，观察相邻下标的关系：

• 当 i = n-1 时：i 右侧无元素，乘积为 1（乘法单位元），故 g[n-1] = 1； （与f的计算方向相反，但思路类似）
• 当 i = n-2 时：g[n-2] 是 n-1 ~ n-1 的积（即 nums[n-1]），而 g[n-1] = 1，因此 g[n-2] = g[n-1] × nums[n-1]；
• 当 i = n-3 时：g[n-3] 是 n-2 ~ n-1 的积（即 nums[n-2]×nums[n-1]），而 g[n-2] = nums[n-1]，因此 g[n-3] = g[n-2] × nums[n-2]；
• 以此类推，对 i ≤ n-2：g[i] 的区间（i+1 ~ n-1）= g[i+1] 的区间（i+2 ~ n-1）× 新增元素 nums[i+1]。

最终递推公式：g[i] = g[i+1] × nums[i+1]（i 从 n-2 到 0）。

边界情况如何处理？
“不包含当前下标”的定义，让边界情况被天然覆盖，无需额外判断：

• 当 i=0（最左端）：f[0] = 1（左侧无元素，积为1），g[0] 是 1 ~ n-1 的积，answer[0] = 1 × g[0]（正确）；
• 当 i = n-1（最右端）：g[n-1] = 1（右侧无元素，积为1），f[n-1] 是 0 ~ n-2 的积，answer[n-1] = f[n-1] × 1（正确）；
• 当 0 < i < n-1（中间下标）：直接用 f[i] × g[i]，无需任何调整。

这正是“不包含当前下标”定义的优势——所有下标用同一套公式，避免边界判断的冗余代码。

代码实现

基础版：用两个辅助数组（易于理解）

我们逐行解析其执行过程，以示例 nums = [1,2,3,4] 为例：

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        // 1. 初始化前缀积数组 f 和后缀积数组 g，默认值为1（乘法单位元）
        vector<int> f(n, 1);  
        vector<int> g(n, 1);  

        // 2. 计算前缀积 f：从左往右，f[i] = f[i-1] * nums[i-1]
        for (int i = 1; i < n; i++) {
            f[i] = f[i-1] * nums[i-1];
        }
        // 示例中 f 的计算过程：
        // i=1: f[1] = f[0] * nums[0] = 1*1 = 1
        // i=2: f[2] = f[1] * nums[1] = 1*2 = 2
        // i=3: f[3] = f[2] * nums[2] = 2*3 = 6
        // 最终 f = [1, 1, 2, 6]

        // 3. 计算后缀积 g：从右往左，g[i] = g[i+1] * nums[i+1]
        for (int i = n - 2; i >= 0; i--) {
            g[i] = g[i+1] * nums[i+1];
        }
        // 示例中 g 的计算过程：
        // i=2: g[2] = g[3] * nums[3] = 1*4 = 4
        // i=1: g[1] = g[2] * nums[2] = 4*3 = 12
        // i=0: g[0] = g[1] * nums[1] = 12*2 = 24
        // 最终 g = [24, 12, 4, 1]

        // 4. 计算结果：answer[i] = f[i] * g[i]
        vector<int> ret(n, 1);
        for (int i = 0; i < n; i++) {
            ret[i] = f[i] * g[i];
        }
        // 示例中 ret 的计算：
        // ret[0] = 1*24 = 24, ret[1] = 1*12 = 12, ret[2] = 2*4 = 8, ret[3] = 6*1 = 6
        // 最终 ret = [24, 12, 8, 6]（正确）

        return ret;
    }
};

基础版复杂度分析

• 时间复杂度：O(n)。三次遍历数组（计算 f、计算 g、计算 ret），每次遍历均为 O(n)，总时间为 3O(n) = O(n)，满足题目要求；
• 空间复杂度：O(n)。使用了 f 和 g 两个辅助数组，每个大小为 n，不符合进阶的“O(1) 额外空间”要求，但易于理解，是进阶版的基础。

进阶版：优化到 O(1) 额外空间

题目允许“answer 数组不作为额外空间”，因此我们可以复用 answer 数组，先存储前缀积，再用一个变量存储后缀积的临时结果，逐步更新 answer，彻底去掉 g 数组：

优化思路

1. 用 answer 数组代替 f 数组，先计算并存储前缀积；
2. 用一个变量 right_product 代替 g 数组，从右往左遍历，实时计算“当前右侧的乘积”；
3. 遍历过程中，answer[i] = answer[i]（前缀积） × right_product（当前右侧积），然后更新 right_product（乘以当前 nums[i]，为下一个左侧元素的右侧积做准备）。

优化版代码

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> answer(n, 1);  // 复用 answer 存储前缀积，代替 f 数组

        // 1. 第一步：计算前缀积，存储到 answer 中（此时 answer[i] = f[i]）
        for (int i = 1; i < n; i++) {
            answer[i] = answer[i-1] * nums[i-1];
        }
        // 示例中 answer 此时为 [1, 1, 2, 6]（与基础版的 f 相同）

        // 2. 第二步：用变量 right_product 计算后缀积，实时更新 answer
        int right_product = 1;  // 初始值为1（最右端元素的右侧积为1）
        // 从右往左遍历，先更新 answer[i]，再更新 right_product
        for (int i = n - 1; i >= 0; i--) {
            answer[i] = answer[i] * right_product;  // 前缀积 × 当前右侧积
            right_product = right_product * nums[i]; // 更新右侧积（加入当前元素，为下一个i-1服务）
        }
        // 示例中遍历过程：
        // i=3: answer[3] = 6 * 1 = 6；right_product = 1*4 = 4
        // i=2: answer[2] = 2 * 4 = 8；right_product = 4*3 = 12
        // i=1: answer[1] = 1 * 12 = 12；right_product = 12*2 = 24
        // i=0: answer[0] = 1 * 24 = 24；right_product = 24*1 = 24
        // 最终 answer = [24, 12, 8, 6]（正确）

        return answer;
    }
};

进阶版复杂度分析

• 时间复杂度：O(n)。仅两次遍历数组（计算前缀积、计算最终结果），总时间 O(n)；
• 空间复杂度：O(1)。除了输出数组 answer，仅使用一个变量 right_product，完全满足进阶要求。

关键细节总结

1. 乘法单位元的选择：前缀积和后缀积的初始值必须为 1，而非 0（加法用 0，乘法用 1，因 x×1 = x，不改变乘积结果）。若初始值设为 0，所有乘积结果都会被清零，完全错误。
2. 遍历方向的正确性：前缀积需从左往右（逐步积累左侧元素的乘积），后缀积需从右往左（逐步积累右侧元素的乘积），方向错误会导致区间覆盖错误（如前缀积从右往左算，会包含右侧元素，不符合“左侧积”定义）。
3. 数组复用的核心：进阶版的关键是“先用 answer 存前缀积，再用变量实时计算后缀积并覆盖更新”。这种“复用输出空间”的思路不仅能优化空间复杂度，还能锻炼“减少冗余存储”的思维——在后续动态规划、前缀和的空间优化中，类似“用原数组存中间结果”的逻辑会频繁出现。
4. 处理0的正确性：无需单独判断数组中的0元素。因为“前缀积+后缀积”的逻辑天然覆盖0的场景：若 nums[i] = 0，则 f[i] 是左侧所有元素的积（不含0），g[i] 是右侧所有元素的积（不含0），answer[i] = f[i]×g[i]（正确）；若 nums 中其他位置有0，则 f[i] 或 g[i] 会包含0，导致 answer[i] = 0（正确）。例如示例2中 nums = [-1,1,0,-3,3]，answer[0] = f[0]×g[0] = 1 × (1×0×(-3)×3) = 0，完全符合预期。

下题预告

掌握了“前缀积+后缀积”的预计算逻辑后，我们将迎来一道“前缀和+同余定理”的经典题——力扣 974. 和可被 K 整除的子数组。

这道题的核心场景是：“统计数组中所有和可被 K 整除的非空连续子数组的个数”，其难点在于：

1. 直接暴力枚举所有子数组会超时（时间复杂度 O(n²)），必须用前缀和优化；
2. 需要结合“同余定理”将“子数组和可被 K 整除”转化为“两个前缀和模 K 相等”，从而快速统计符合条件的前缀和对；
3. 需处理“负余数”的边界问题（如 (-1) mod 5 = 4，而非 -1），避免统计遗漏。

这道题是前缀和思想的重要拓展——从“直接计算区间和”升级到“利用数学性质转化问题”，同时衔接了数论中的同余知识，是数组统计类问题的高频考点。提前预习“前缀和模 K”的概念，能更好地理解明天的解题思路～

如果今天的“前缀积优化”讲解帮你理清了从基础版到进阶版的逻辑，尤其是掌握了“复用输出数组降空间”的技巧，别忘了点赞收藏！下次遇到“除自身外乘积”“区间积统计”类题目时，就能快速回忆起核心递推公式和优化思路。关注博主，明天一起攻克“前缀和+同余”的难题，逐步扎实数组算法的核心能力～