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

题目:238.除自身以外数组的乘积

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

题目数据 保证 数组 nums 之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

• 示例 1：

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

• 示例 2：

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

• 提示：

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内

• 进阶：

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

思路

要解决这个问题，可以使用前缀积和后缀积的方法。这种方法通过两次遍历数组，分别计算前缀积和后缀积，然后结合这两个结果计算出每个位置的答案。

具体步骤如下：

1. 初始化两个数组 left 和 right，用于存储每个位置的前缀积和后缀积。
2. 遍历数组，计算每个位置的前缀积并存储在 left 中。
3. 再次遍历数组，计算每个位置的后缀积并存储在 right 中。
4. 最后，根据前缀积和后缀积计算出每个位置的答案。

• 时间复杂度:O(n)
• 空间复杂度:O(n)

代码

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int[] left = new int[n];
    left[0] = 1;
    int[] right = new int[n];
    right[n - 1] = 1;
    // 初始化结果数组
    int[] result = new int[n];
    // 计算每个位置的左边累积乘积
    for (int i = 1; i < n; i++) {
        left[i] = nums[i - 1] * left[i - 1];
    }
    // 计算每个位置的右边累积乘积
    for (int i = n - 2; i >= 0; i--) {
        right[i] = nums[i + 1] * right[i + 1];
    }
    // 计算结果数组，每个位置的值等于左边累积乘积乘以右边累积乘积
    for (int i = 0; i < n; i++) {
        result[i] = left[i] * right[i];
    }
    return result;
}

思路2

进一步优化可以避免使用额外的空间来存储前缀和后缀积数组，从而将空间复杂度降低到 O(1)（不计输出数组所占空间）。我们可以利用结果数组 result 来存储左边的累积乘积，然后在第二次遍历时直接更新 result，计算出每个位置的最终值。

优化后的步骤如下：

1. 首先计算每个位置的左边累积乘积，并存储在 result 数组中。
2. 然后计算每个位置的右边累积乘积，并直接更新 result 数组中的值。

• 时间复杂度:O(n)
• 空间复杂度:O(1)

代码

public int[] productExceptSelf(int[] nums) {
    int n = nums.length;
    int right = 1;
    // 初始化结果数组
    int[] result = new int[n];
    result[0] = 1;
    // 计算每个位置的左边累积乘积，并存储在结果数组中
    for (int i = 1; i < n; i++) {
        result[i] = nums[i - 1] * result[i - 1];
    }
    // 计算右边累积乘积，并直接更新结果数组
    for (int i = n - 1; i >= 0; i--) {
        result[i] = result[i] * right;
        right = right * nums[i];
    }
    return result;
}