LeetCode Hot 100 | 16. 除了自身以外数组的乘积

LeetCode 238. 除自身以外数组的乘积 (Product of Array Except Self)

1. 核心思路：左右乘积列表 (Left & Right Products)

形式化定义：

题目要求不能使用除法，且时间复杂度为 $O(N)$。我们将问题拆解为两部分：

$Answer[i] = (\text{左侧所有数的乘积}) \times (\text{右侧所有数的乘积})$

$Answer[i] = L[i] \times R[i]$

• 前缀积 ($L[i]$)：索引 $i$ 左侧所有元素的乘积（下标 $0$ 到 $i-1$）。

• 后缀积 ($R[i]$)：索引 $i$ 右侧所有元素的乘积（下标 $i+1$ 到 $n-1$）。

---

2. 代码实现 (基础版：空间 $O(N)$)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        
        // L[i] 代表 i 左侧所有元素的乘积
        // R[i] 代表 i 右侧所有元素的乘积
        vector<int> L(n, 1);
        vector<int> R(n, 1);
        
        // 1. 从左向右扫：计算前缀积
        // L[0] 左边没数，默认为 1
        for (int i = 1; i < n; i++) {
            L[i] = L[i - 1] * nums[i - 1];
        }
        
        // 2. 从右向左扫：计算后缀积
        // R[n-1] 右边没数，默认为 1
        for (int i = n - 2; i >= 0; i--) {
            R[i] = R[i + 1] * nums[i + 1];
        }
        
        // 3. 合并结果
        vector<int> result(n);
        for (int i = 0; i < n; i++) {
            result[i] = L[i] * R[i];
        }
        
        return result;
    }
};

---

3. 进阶优化：空间 $O(1)$ (原地计算)

面试高频考点：题目通常会进阶要求"常数空间复杂度"（输出数组不算在额外空间内）。

优化策略：

1. 复用：直接用输出数组 result 来充当 L 数组。

2. 动态计算：R 数组不需要显式存储。我们可以在从右向左扫描时，用一个变量 R 动态维护当前的右侧乘积，并直接乘到 result[i] 上。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n, 1); // 先初始化为 1
        
        // 1. 计算左侧乘积 (直接存入 result)
        // 此时 result[i] 实际上就是 L[i]
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }
        
        // 2. 动态计算右侧乘积，并直接乘入结果
        int R = 1; // R 代表当前位置右边的乘积滚雪球
        for (int i = n - 1; i >= 0; i--) {
            // 当前结果 = (已存的左积) * (动态的右积)
            result[i] = result[i] * R;
            
            // 更新 R，为下一个位置做准备
            R *= nums[i];
        }
        
        return result;
    }
};

---

4. 关键细节备忘

1. 初始化陷阱：

   • 乘法的单位元是 1，不是 0。所有的 L、R、result 初始化都必须是 1，否则乘积全变 0。

2. 边界处理：

   • 左扫时，i 从 1 开始（因为第 0 个左边没数）。

   • 右扫时，i 从 n-2 开始（因为第 n-1 个右边没数）。

   • 但在 $O(1)$ 优化版中，右扫通常从 n-1 开始配合 R=1 比较顺手，逻辑更统一。

3. 思想迁移：

   • 这道题本质是 DP (动态规划) 的简化版，或者是 前缀和 (Prefix Sum) 的变体。

   • 如果你遇到"除自身以外数组的和"，解法完全一样（把乘号改成加号，初始值改为 0）。