238. 除了自身以外数组的乘积

✨核心逻辑

本题要求在 不使用除法 且 时间复杂度 O(N) 的前提下，计算出数组中每个元素除自身以外其他元素的乘积。这里提供两种解法：

思路一：左右乘积数组。分别计算出每个元素左侧所有元素的乘积（前缀积）和右侧所有元素的乘积（后缀积），最后将两者相乘。此方法简单直观，但空间复杂度较高。

🔥代码实现（含详细变量注释）

package array_string;

public class productExceptSelf_238 {

    // 思路 1：左右乘积数组（时间 O(N)，空间 O(N)）
    public int[] productExceptSelf(int[] nums) {
        // n：记录数组的长度
        int n = nums.length;

        // left：前缀积数组，用于存储每个位置左侧所有元素的乘积
        int[] left = new int[n];
        left[0] = 1; // 第一个元素左侧没有元素，乘积初始化为 1

        // right：后缀积数组，用于存储每个位置右侧所有元素的乘积
        int[] right = new int[n];
        right[n - 1] = 1; // 最后一个元素右侧没有元素，乘积初始化为 1

        // 1. 从左向右遍历，填充 left 数组
        for (int i = 1; i < n; i++) {
            left[i] = left[i - 1] * nums[i - 1];
        }

        // 2. 从右向左遍历，填充 right 数组
        for (int index = n - 2; index >= 0; index--) {
            right[index] = right[index + 1] * nums[index + 1];
        }

        // 3. 将 left 和 right 对应的位置相乘，得到最终结果，并直接覆盖原数组返回
        for (int i = 0; i < right.length; i++) {
            nums[i] = left[i] * right[i];
        }
        return nums;
    }

⏱️复杂度分析:----思路 1（左右数组)
- 时间复杂度：O(N)，需遍历数组 3 次。
- 空间复杂度：O(N)，额外使用了两个长度为 N 的数组 left 和 right

思路二：空间优化（O(1) 额外空间）。先利用输出数组（result）存储每个元素的前缀积。然后定义一个变量 right 从右向左遍历，动态维护当前元素右侧所有元素的乘积，直接在 result 数组上乘以 right，从而达到节省额外空间的目的。


    // 进阶思路 2：空间优化（时间 O(N)，额外空间 O(1)）
    public int[] productExceptSelf1(int[] nums) {
        int n = nums.length;

        // result：结果数组。我们先利用它来存储前缀积，最后再将其转化成最终答案
        int[] result = new int[n];
        result[0] = 1; // 第一个元素左侧没有元素，乘积为 1

        // 1. 从左向右遍历，把每个元素左侧的乘积保存到 result 数组中
        for (int i = 1; i < n; i++) {
            result[i] = result[i - 1] * nums[i - 1];
        }

        // right：定义动态变量，用于记录当前元素右侧所有元素的累积乘积
        // 初始状态为 1，因为最右侧（n-1）元素的右侧没有元素，相当于乘 1
        int right = 1;
        
        // 2. 从右向左遍历，将 result（前缀积）和动态维护的 right（后缀积）相乘
        for (int index = n - 1; index >= 0; index--) {
            result[index] = result[index] * right; // 前缀积 * 右侧累积乘积 = 最终结果
            right *= nums[index]; // 更新 right，把当前的 nums[index] 乘进去，用于下一次循环计算更左边的元素
        }
        
        return result;
    }
}