016除了自身以外数组的乘积

除了自身以外数组的乘积

题目链接：https://leetcode.cn/problems/product-of-array-except-self/description/?envType=study-plan-v2&envId=top-100-liked

我的解答：

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

分析：代码的时间复杂度为O(n)，空间复杂度为O(n)。思路：用两个数组分别保存每个数的前缀乘积和后缀乘积，每个元素可以根据自身的前缀乘积和后缀乘积得出答案。

看了官方题解后的解答：

//方法一与我的解答相同 //方法二：空间复杂度 O(1) 的方法 //算法思想与方法一相同，只是利用输出数组将空间复杂度从O(n)优化为了O(1) //注意：输出数组不算在空间复杂度内 public int[] productExceptSelf(int[] nums) { int n=nums.length; int[] ans = new int[n];//先将输出数组当作后缀乘积数组 int before=1;//维护每个数的前缀乘积 ans[n-1]=1; for(int i=n-2; i>=0; i--){ ans[i]=nums[i+1]*ans[i+1]; } for(int i=0; i<n; i++){ ans[i]*=before; before*=nums[i]; } return ans; }

分析：

​ 1、代码的时间复杂度为O(n)，空间复杂度为O(1)。

​ 2、方法二利用输出数组维护后缀乘积，在得到答案的同时用一个变量维护每个元素的前缀乘积，从而将空间复杂度从方法一的O(n)优化为了O(1)。

总结

• 本题的思路比较简单，很容易做对，但是在做对题的基础上对空间复杂度进行进一步优化的方案可能不太容易想到。