LeetCode 238题「除自身以外数组的乘积」

LeetCode 238题「除自身以外数组的乘积」要求在不使用除法的情况下，计算数组中每个元素除自身以外的所有元素的乘积。以下是对该问题的详细解析，包括解题思路和C++代码实现：

题目描述

给你一个整数数组 nums，返回一个数组 answer，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

示例：

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

限制条件：

• 2 <= nums.length <= 10^5
• -30 <= nums[i] <= 30
• 不允许使用除法，且时间复杂度应为 $O(n)$。

解题思路

本题的关键在于不使用除法且在 $O(n)$ 时间内完成计算。可以通过两次遍历数组，分别计算每个元素左侧和右侧的乘积，然后将两侧乘积相乘得到结果。

方法：左右乘积数组

核心思路：

1. 左乘积数组 left：left[i] 表示 nums[i] 左侧所有元素的乘积（不包含 nums[i]）。
2. 右乘积数组 right：right[i] 表示 nums[i] 右侧所有元素的乘积（不包含 nums[i]）。
3. 结果数组：answer[i] = left[i] * right[i]。

步骤：

1. 计算左乘积数组：
   从左到右遍历 nums，left[0] = 1，后续元素的左乘积为前一个元素的左乘积乘以其值。

   left[i] = left[i-1] * nums[i-1]
   

2. 计算右乘积数组：
   从右到左遍历 nums，right[n-1] = 1，后续元素的右乘积为后一个元素的右乘积乘以其值。

   right[i] = right[i+1] * nums[i+1]
   

3. 合并结果：
   遍历 nums，将每个元素的左乘积和右乘积相乘得到结果。

C++代码：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n, 1);
        vector<int> right(n, 1);
        vector<int> answer(n);
        
        // 计算左乘积数组
        for (int i = 1; i < n; ++i) {
            left[i] = left[i-1] * nums[i-1];
        }
        
        // 计算右乘积数组
        for (int i = n-2; i >= 0; --i) {
            right[i] = right[i+1] * nums[i+1];
        }
        
        // 合并结果
        for (int i = 0; i < n; ++i) {
            answer[i] = left[i] * right[i];
        }
        
        return answer;
    }
};

优化：空间复杂度 $O(1)$

核心思路：
不使用额外的 left 和 right 数组，直接在结果数组上进行计算，从而将空间复杂度优化到 $O(1)$（不包含结果数组）。

步骤：

1. 计算左乘积：
   直接将左乘积存储在 answer 中。

2. 计算右乘积并合并：
   使用一个变量 right 动态记录当前元素的右乘积，从右到左遍历并更新 answer。

C++代码：

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> answer(n, 1);
        
        // 计算左乘积并存储在answer中
        for (int i = 1; i < n; ++i) {
            answer[i] = answer[i-1] * nums[i-1];
        }
        
        // 动态计算右乘积并合并
        int right = 1;
        for (int i = n-1; i >= 0; --i) {
            answer[i] *= right;
            right *= nums[i];  // 更新右乘积
        }
        
        return answer;
    }
};

复杂度分析

示例演示（以 nums = [1,2,3,4] 为例）

左右乘积数组方法：

1. 计算左乘积数组：

   left = [1, 1, 2, 6]
   

2. 计算右乘积数组：

   right = [24, 12, 4, 1]
   

3. 合并结果：

   answer[i] = left[i] * right[i]
   answer = [1*24, 1*12, 2*4, 6*1] = [24, 12, 8, 6]
   

空间优化方法：

1. 计算左乘积：

   answer = [1, 1, 2, 6]
   

2. 动态计算右乘积并合并：

   • i = 3，right = 1，answer[3] = 6*1 = 6，right = 1*4 = 4
   • i = 2，right = 4，answer[2] = 2*4 = 8，right = 4*3 = 12
   • i = 1，right = 12，answer[1] = 1*12 = 12，right = 12*2 = 24
   • i = 0，right = 24，answer[0] = 1*24 = 24

关键细节

1. 初始化：
   左乘积数组和右乘积数组的初始值均为 1，因为没有元素时乘积为 1。

2. 遍历方向：
   左乘积从左到右计算，右乘积从右到左计算，确保每个元素的左右乘积不包含自身。

3. 空间优化：
   通过复用结果数组和单个变量 right，将空间复杂度优化到 $O(1)$。

总结

本题通过两次遍历数组分别计算左右乘积，巧妙地在不使用除法的情况下实现了 $O(n)$ 的时间复杂度。空间优化版本进一步将空间复杂度降至 $O(1)$，是该问题的最优解法。