leetcode热题HOT 238. 除自身以外数组的乘积

一、问题描述：

给你一个整数数组 nums，返回 数组 answer ，其中 answer[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]

二、解题思路：

1. 利用前缀乘积和后缀乘积的方法能够在 O(n) 的时间复杂度内解决问题，避免使用嵌套循环来计算乘积。
2. 具体步骤：
   ①在第一次遍历中，先将结果数组 res 的第一个元素设为1，然后从第二个元素开始，将当前位置的值设为前一个位置的值乘以前一个元素的值，即 res[i] = res[i - 1] * nums[i - 1]，这样 res[i] 就记录了当前位置之前所有元素的乘积。
   ②在第二次遍历中，定义变量 next 初始值为1，从数组末尾开始遍历数组，每次将当前位置的元素值乘上 next，这样就得到了后缀乘积，最终的结果为前缀乘积与后缀乘积的乘积。

三、代码示例：

//时间复杂度为 O(n)
class Solution {
    public int[] productExceptSelf(int[] nums) {
    int[] res = new int[nums.length];
    //int pre = 1;
    res[0] = 1;
    for(int i = 1; i < nums.length; i++){
        //res[i] = pre;  
        //pre *= nums[i]; //前缀乘积
        res[i] = res[i - 1] * nums[i - 1];
        //System.out.println(res[i]);
    }
    int next = 1;
    for(int j = nums.length - 1; j >= 0; j--){
        res[j] = res[j] * next; //前缀乘后缀
        next *= nums[j];  //后缀乘积
        //System.out.println(res[j]);
    }
    return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 时间复杂度分析：这段代码需要两次遍历数组，所以时间复杂度为 O(n)，其中 n 为数组的长度。
  空间复杂度 O(1)。

四、补充与总结：

利用前缀乘积：
第一次遍历计算每个元素的前缀乘积，并将结果存储在数组 res 中，这样 res[i] 就表示了位置 i 左侧所有元素的乘积。这种方法避免了在每次计算位置 i 时都重新计算左侧所有元素的乘积。
利用后缀乘积：
第二次遍历时，从数组末尾开始计算每个元素的后缀乘积，并将其乘到之前计算得到的前缀乘积中，最终得到的结果即为除自身以外数组中所有元素的乘积。这种方法避免了在每次计算位置 i 时都重新计算右侧所有元素的乘积。