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]提示2 nums.length 105-30 nums[i] 30输入保证数组answer[i]在32 位整数范围内进阶你可以在O(1)的额外空间复杂度内完成这个题目吗 出于对空间复杂度分析的目的输出数组不被视为额外空间。题目分析这道题难点在于不能使用除法因此我们需要转换一下思路。从最终答案结果来看我们其实可以把每一个数拆成两部分左侧数之积与右侧数之积即除自身以外的乘积 左边所有元素成绩 * 右边所有元素乘积nums [1,2,3,4]答案[24,12,8,6]24 2*3*412 1*3*48 1*2*46 1*2*3根据这个思路我们可以分别正向、反向遍历数组每次遍历累乘数字之积最后将这两部分的数乘起来就可以得到我们需要的答案优化技巧我们可以做到最多使用一个额外的列表第一次遍历的同时我们就将累乘的结果顺带放到数组中反向遍历时顺带乘回去这样就可以使用一个额外列表完成所有操作。空间优化更极端的情况就是利用原数组直接存放每个数字的累乘结果再额外申请一个变量来存放数组中第一个/最后一个元素的值这取决于你的遍历顺序这种情况下额外空间压缩到O1级别是最优解本题解仅进行了初步优化额外空间为On代码展示class Solution: def productExceptSelf(self, nums: List[int]) - List[int]: n_len len(nums) answer [1] * n_len lefr_a 1 right_a 1 for i in range(n_len): answer[i] * lefr_a lefr_a * nums[i] for i in range(n_len)[::-1]: answer[i] * right_a right_a * nums[i] return answer