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

思路：

一、前后缀分解

1.answer[i]等于nums中除了nums[i]之外的其余各元素的乘积。换句话说，如果知道了i左边所有数的乘积，以及i右边所有数的乘积，就可以算出answer[i]。

2.定义pre[i]和post[i]：

（1）定义pre[i]表示从nums[0]到nums[i -1]的乘积。

（2）定义post[i]表示从nums[i + 1]到nums[n - 1]的乘积。

3.计算pre[i]和post[i]：

（1）要计算pre[i]，可以先计算出nums[0]到nums[2]的乘积pre[i - 1]，再乘上nums[i - 1]，就得到了pre[i]。即pre[i] = pre[i - 1] * nums[i - 1]。

（2）同理可得，post[i] = post[i + 1] * nums[i + 1]。

4.设置初始值：pre[0] = post[n - 1] = 1。

5.所求结果answer[i] = pre[i] * post[i]。

6.复杂度分析：

（1）时间复杂度：O(n)，其中n是nums的长度。

（2）空间复杂度：O(n)。

附代码：

class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; int[] pre = new int[n]; pre[0] = 1; for(int i = 1;i < n;i++){ pre[i] = pre[i - 1] * nums[i - 1]; } int[] post = new int[n]; post[n - 1] = 1; for(int i = n - 2;i >= 0;i--){ post[i] = post[i + 1] * nums[i + 1]; } int[] ans = new int[n]; for(int i = 0;i < n;i++){ ans[i] = pre[i] * post[i]; } return ans; } }

二、优化先后缀分解（不使用额外空间）

1.思路：先计算post，然后一边计算pre，一边把pre直接乘到post[i]中，最后返回post。由于题目中说明输出数组不被视为额外空间，所以该做法的空间复杂度为O(1)。此外，这种做法可以少遍历一次。

2.复杂度分析：

（1）时间复杂度：O(n)，其中n是nums的长度。

（2）空间复杂度：O(1)，返回值不计入。

附代码：

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