4.4 前缀和专题：LeetCode 238. 除自身以外数组的乘积

1. 题目链接

• LeetCode 238. 除自身以外数组的乘积
  题目链接

2. 题目描述

• 输入：一个整数数组 nums。
• 输出：返回一个数组 ret，其中 ret[i] 表示 nums 中除 nums[i] 外所有元素的乘积。
• 要求：
  • 时间复杂度为 O(n)。
  • 不能使用除法运算。

3. 示例分析

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

• 对于 i=0，乘积为 2*3*4 = 24；
• 对于 i=1，乘积为 1*3*4 = 12，依此类推。

示例 2：
输入：nums = [-1, 1, 0, -3, 3]
输出：[0, 0, 9, 0, 0]
解释：

• 由于数组中有 0，大部分结果会为 0。

4. 算法思路

前缀积算法

1. 预处理阶段：

   • 构建两个数组 f 和 g：
     • f[i] 表示前 i 个元素（即 nums[0] 到 nums[i-1]）的乘积。
     • g[i] 表示后 n-i-1 个元素（即 nums[i+1] 到 nums[n-1]）的乘积。
   • 递推公式：

     f[i] = f[i-1] * nums[i-1]  // 从左到右累乘  
     g[i] = g[i+1] * nums[i+1]  // 从右到左累乘  
     

   • 时间复杂度：O(n)。

2. 计算阶段：

   • 遍历每个下标 i，结果 ret[i] = f[i] * g[i]。
   • 时间复杂度：O(n)。

暴力枚举法

• 对于每个下标 i，遍历数组两次：

  vector<int> ret(n, 1);  
  for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) 
          if (j != i) ret[i] *= nums[j];   
  

• 时间复杂度：O(n²)。

5. 边界条件与注意事项

1. 零值处理：若数组中有多个零，结果中大部分元素会为零（需避免零值的重复计算）。

2. 数值溢出：使用 int 存储乘积可能导致溢出，但题目未明确限制输入范围。

3. 空间优化：代码未满足空间复杂度 O(1) 的进阶要求。若需优化，可用输出数组 ret 直接存储前缀积， 再反向遍历计算后缀积。

4. 索引范围：f[0] 和 g[n-1] 初始化为 1（空数组的乘积为 1）。

6. 代码实现

class Solution 
{
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        int n = nums.size();
        vector<int> f(n, 1), g(n, 1);
        
        // 计算前缀积 f[i] = nums[0] * nums[1] * ... * nums[i-1]
        for (int i = 1; i < n; i++) {
            f[i] = f[i-1] * nums[i-1];
        }
        
        // 计算后缀积 g[i] = nums[i+1] * nums[i+2] * ... * nums[n-1]
        for (int i = n-2; i >= 0; i--) {
            g[i] = g[i+1] * nums[i+1];
        }
        
        // 合并结果
        vector<int> ret(n);
        for (int i = 0; i < n; i++) {
            ret[i] = f[i] * g[i];
        }
        return ret;
    }
};

7. 对比图表：前缀积 vs 暴力枚举

8. 总结

• 前缀积算法通过预处理将时间复杂度优化到 O(n)，是解决该问题的标准方法。
• 暴力枚举法虽然空间占用低，但时间复杂度高，仅适用于极小数据规模。