【LeetCode 热题 100】238. 除自身以外数组的乘积——（解法二）前缀积与后缀积+优化空间复杂度

Problem: 238. 除自身以外数组的乘积
题目：给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。

【LeetCode 热题 100】238. 除自身以外数组的乘积——（解法一）前缀积与后缀积

整体思路

这段代码同样旨在解决 “除自身以外数组的乘积” 的问题，但它是一个空间复杂度更优的版本。它巧妙地复用了结果数组（在此代码中是sufMulti数组）来存储中间计算结果，从而避免了额外开辟一个前缀积数组，将空间复杂度从 O(N) 降低到了 O(1)（如果不考虑输出数组）。

算法的核心思路依然是 前缀积与后缀积 的结合，但实现方式更为精妙：

1. 第一遍遍历（从右到左）：计算后缀积

   • 算法首先创建一个结果数组，在此代码中它被命名为 sufMulti，但我们应将其理解为最终的 ans 数组。
   • 通过一次从右到左的遍历，计算出所有位置的后缀积并存入这个数组。
   • 具体地，sufMulti[i] 被赋值为 nums[i+1...n-1] 的乘积。
   • 这个循环结束后，sufMulti 数组的状态是：sufMulti[i] 等于 nums[i] 右侧所有元素的乘积。

2. 第二遍遍历（从左到右）：结合前缀积

   • 算法不再创建一个独立的前缀积数组，而是使用一个单独的变量 preMulti 来动态地计算前缀积。
   • preMulti 在循环开始前初始化为 1（代表索引0左侧的空前缀积）。
   • 接着，进行一次从左到右的遍历。在循环的第 i 步：
     a. 合成结果：此时的 sufMulti[i] 存储的是后缀积，而 preMulti 存储的是 nums[0...i-1] 的前缀积。将两者相乘 sufMulti[i] *= preMulti，就得到了 ans[i] 的最终结果，并直接更新到 sufMulti 数组的 i 位置上。
     b. 更新前缀积：为了下一次循环 (i+1) 做准备，需要更新前缀积，使其包含 nums[i]。执行 preMulti *= nums[i]，这样在下一次循环开始时，preMulti 就代表了 nums[0...i] 的乘积。

3. 返回结果

   • 当第二遍遍历结束后，sufMulti 数组已经被完全更新为最终的答案，直接将其返回即可。

这种方法通过“两趟遍历、一个变量”的方式，巧妙地完成了前缀积和后缀积的计算与合并，是此问题的标准最优解。

完整代码

class Solution {
    /**
     * 计算一个数组，其中 ans[i] 等于 nums 中除 nums[i] 之外所有元素的乘积。
     * (空间优化版)
     * @param nums 输入的整数数组
     * @return 结果数组
     */
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        // sufMulti 数组在这里被复用，它将先存储后缀积，最终变为我们的答案数组 ans。
        int[] sufMulti = new int[n];
        
        // 步骤 1: 从右到左计算后缀积，并存入 sufMulti 数组。
        
        // 基础情况：最后一个元素的后缀积是 1（其右侧没有元素）。
        sufMulti[n - 1] = 1;
        // 从倒数第二个元素开始，向前计算后缀积。
        for (int i = n - 2; i >= 0; i--) {
            // sufMulti[i] 等于其右边一个位置的后缀积乘以右边一个位置的元素值。
            sufMulti[i] = sufMulti[i + 1] * nums[i + 1];
        }
        
        // 步骤 2: 从左到右遍历，结合动态计算的前缀积，合成最终结果。
        
        // preMulti: 一个变量，用于动态记录当前位置左侧所有元素的前缀积。
        // 初始化为 1，代表索引 0 左侧的空前缀积。
        int preMulti = 1;
        for (int i = 0; i < n; i++) {
            // a. 合成结果:
            //    此时 sufMulti[i] 存储的是原始的后缀积。
            //    preMulti 存储的是 nums[0...i-1] 的前缀积。
            //    将两者相乘，直接更新到 sufMulti[i] 中，得到最终结果。
            sufMulti[i] *= preMulti;
            
            // b. 更新前缀积:
            //    为了下一次循环 (i+1)，将当前元素 nums[i] 乘入 preMulti。
            preMulti *= nums[i];
        }
        
        // 此时，sufMulti 数组已经包含了最终的答案。
        return sufMulti;
    }
}

时空复杂度

时间复杂度：O(N)

1. 后缀积计算：第一个 for 循环从 n-2 遍历到 0，执行了 N-1 次操作。时间复杂度为 O(N)。
2. 结果合成与前缀积计算：第二个 for 循环从 0 遍历到 n-1，执行了 N 次操作。时间复杂度为 O(N)。

综合分析：
算法由两个独立的、不嵌套的线性扫描组成。总的时间复杂度是 O(N) + O(N) = O(N)。

空间复杂度：O(1) (不考虑输出数组)

1. 主要存储开销：
   • int[] sufMulti = new int[n]: 这个数组被用作最终的输出。在许多算法复杂度分析的约定中，返回结果所需的空间不计入额外辅助空间。
   • int preMulti: 这是一个单一的整型变量。

综合分析：
如果我们遵循不计算输出数组空间的约定，那么算法只使用了 preMulti 等几个常数级别的变量。因此，其额外辅助空间复杂度为 O(1)。这是该解法相比于上一个版本的主要优势。如果必须计算输出数组，则空间复杂度为 O(N)。

参考灵神