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*4）
12 = （1）*（3*4）8 = （1*2）*（4）
6 = （1*2*3）
根据这个思路，我们可以分别正向、反向遍历数组，每次遍历累乘数字之积，最后将这两部分的数乘起来，就可以得到我们需要的答案
优化技巧
我们可以做到最多使用一个额外的列表，第一次遍历的同时我们就将累乘的结果顺带放到数组中，反向遍历时顺带乘回去，这样就可以使用一个额外列表完成所有操作。
空间优化更极端的情况就是利用原数组直接存放每个数字的累乘结果，再额外申请一个变量来存放数组中第一个/最后一个元素的值（这取决于你的遍历顺序），这种情况下额外空间压缩到
O（1）级别，是最优解
本题解仅进行了初步优化，额外空间为O（n）
代码展示
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
