238。Productofarraysotherthanitself来源：LeetCodehttps://leetcode-cn.com/problems/product-of-array-except-self题目给你一个长度为n的整数数组nums，其中n>1，并返回输出数组output，其中output[i]等于nums中除nums[i]之外的其他元素的乘积。示例：输入：[1,2,3,4]输出：[24,12,8,6]提示：标题数据保证所有前缀元素和后缀（甚至整个数组）中任意元素的乘积该数组在32位整数范围内。解释：请不要使用除法，以O(n)的时间复杂度完成这道题。进阶：你能以常量空间复杂度解决这个问题吗？（为了空间复杂度分析，输出数组不考虑额外空间。）解题思路：先看左右商品列表标题中的提示，确保所有前缀和后缀（甚至整个数组）数组中任意一个元素的乘积都在32位整数范围内，所以这里可以忽略数据溢出的问题。再看看说明书。该指令表示不能使用除法。因为，如果要求除当前元素数组的乘积，只要先求出整个数组的乘积，再除以当前元素，就是要求的答案。（当然，这里有个问题，如果当前元素为0，这里要注意，不过不建议往这个方向考虑解决方案，这里就不展开了）本文使用的方法：左右商品列表，这里需要构造left和right两个数组，分别存放当前元素左边的商品和右边的商品。具体构造方法：初始化left和right两个数组。其中left[i]表示i左边所有元素的乘积。right[i]表示i右边所有元素的乘积。开始填充数组。这里需要注意left[0]和right[lenght-1]的值（length表示数组的长度，右边的数组从右往左填充）。对于左数组，left[0]表示原数组中索引为0的元素左边所有元素的乘积。原数组第一个元素左边没有其他元素，所以这里初始化为1。其他元素是：left[i]=left[i-1]*nums[i-1]同一个右数组，right[length-1]表示最后一个元素右边所有元素的乘积原始数组。但是因为最后右边没有其他元素，所以这里right[length-1]也被初始化为1。其他元素为：right[i]=right[i+1]*nums[i+1]对于返回的数组output数组，再次遍历原数组，索引i的值为：output[i]=left[i]*right[i]主要在于左右数组的构造，具体过程如下图所示：具体实现代码见[代码1]部分。上述方法实现后，时间复杂度为O(N)，空间复杂度也为O(N)（N表示数组的长度）。因为构造了左右数组，所以两个数组的长度都是N。对于题目的进阶部分，希望尝试用常量空间复杂度来完成这道题。（这里不计算输出数组的空间）方法还是使用左右积列表的方法，只是这里没有单独构造左右数组。直接在输出数组中构造。具体思路：先将输出数组构造为左数组，再动态构造右数组计算结果。具体方法：先初始化输出数组，先构造为左数组，然后output[i]表示i左边所有元素的乘积。（具体构造方法同上）不过，这里我们不能再单独构造右数组了（前面说了，空间复杂度必须是常数）。我们这里使用的方法是在遍历输出答案的时候维护一个变量right，变量right代表右边元素的乘积。遍历将output[i]的值更新为output[i]*right，将right的值更新为right*nums[i]的意思是遍历下一个元素右边元素的乘积。具体实现代码见【代码2】。代码实现#code1class解决方案：defproductExceptSelf(self,nums:List[int])->List[int]:length=len(nums)left=[0]*lengthright=[0]*lengthoutput=[0]*length#先填充左数组#左数组表示遍历时i左边的乘积#因为数组第一个元素左边没有其他元素，所以左数组第一个元素是1#左数组的下一个元素是原数组第一个元素与左数组第一个元素的乘积，依此类推left[0]=1foriinrange(1,length):left[i]=nums[i-1]*left[i-1]#同一个右数组从右到左填充#同一个数组的尾元素右边没有其他元素，所以的值末尾元素为1#从右往左的元素为原数组与右数组末尾的前一个元素的乘积，依此类推right[length-1]=1foriinrange(length-2,-1,-1):right[i]=nums[i+1]*right[i+1]#再次遍历，输出输出数组#output[i]等于nums中除了nums[之外其他元素的乘积i]#即output[i]的值为left[i]*right[i]foriinrange(length):output[i]=left[i]*right[i]returnoutput#code2class解决方案：defproductExceptSelf(self,nums:List[int])->List[int]:length=len(nums)output=[0]*length#首先构造输出为左积列表#同时将第一个元素初始化为1输出[0]=1foriinrange(1,length):output[i]=output[i-1]*nums[i-1]#维护一个变量权#更新output[i]的值到output[i]*right#同时更新right=right*nums[i]表示遍历到下一个元素右边的乘积（此时从右向左遍历）#初始化right为1right=1foriinrange(length-1,-1,-1):output[i]=output[i]*rightright=right*nums[i]returnoutput实现结果[代码1实现结果][代码2实现结果】总结一下，先看题，排除使用除法的方法，使用左右商品列表相乘的方法来解题。确定方法后，构造左右数组。构造时需要注意的两个元素是left[0]和right[length-1]。left[0]表示原数组索引是0左边所有元素的乘积，但是原数组中索引为0的元素左边没有元素，所以初始化为1。其他元素为：left[i]=left[i-1]*nums[i-1]同理，right[length-1]表示原数组末尾元素右侧的所有商品。这里元素组中最后一个元素的右边没有其他元素，所以right[length-1]也初始化为1。返回的输出数组输出为：output[i]=left[i]*right[i]前面的方法已经足够解决问题了，题目需要进阶尝试解决空间复杂度不变的问题。这里依然是使用左右商品列表的思路。（题目中有说明，输出数组不认为是附加空间）然后先用输出数组构造一个左产品列表，维护一个变量right。遍历并更新output的数组，更新值为output[i]*right（注意：这里遍历时从右向左遍历），在更新output的值的同时，将right的值更新为right*nums[i]，这里是以下迭代值右侧所有元素的乘积。
