LeetCode热题100--238.除自身以外数组的乘积--中等

1. 题目

给你一个整数数组 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]

2. 题解

class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] suf = new int[n];suf[n-1] = 1;for (int i = n-2; i >= 0; i--){suf[i] = suf[i+1] * nums[i+1];}int pre = 1;for(int i = 0; i < n; i++){//此时pre为nums[0]到nums[i-1]的乘积，直接乘到suf[i]中suf[i] *= pre;pre *= nums[i];}return suf;}
}

3. 解析

出自这位老师：灵茶山艾府：前后缀分解，附题单！（Python/Java/C++/C/Go/JS/Rust）

1. class Solution {
   public int[] productExceptSelf(int[] nums)
   这是一段类的定义，这里创建了一个名为"Solution"的解决方案类。
2. int n = nums.length;
   这是将输入数组的长度赋值给变量n。
3. int[] suf = new int[n];
   suf[n-1] = 1;
   for (int i = n-2; i >= 0; i–) {
   suf[i] = suf[i+1] * nums[i+1];
   }
   这段代码是计算右边所有数字的乘积。它首先创建一个与输入数组大小相同的新数组，并将最后一个元素赋值为1（因为没有其他元素可以相乘）。然后从倒数第二个元素开始迭代到第一个元素，在每个位置上计算当前索引右边所有数字的乘积，并将其存储在suf数组对应的位置上。
4. int pre = 1;
   for (int i = 0; i < n; i++) {
   suf[i] *= pre;
   pre *= nums[i];
   }
   这段代码计算左边所有数字的乘积，并与当前位置右边的乘积相乘。它使用两个变量pre来存储这个值（初始为1）和数组suf。在每次迭代中，pre和suf[i]都被更新以包含当前元素左边所有数字的乘积。
5. return suf;
   最后，函数返回结果数组suf。这是输入数组每个位置的除自身外的所有数字的乘积。