题目难度：中等
默认优化目标：最小化平均时间复杂度。
Python默认为Python3。
目录
1 题目描述
给你一个整数数组 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 -
保证 数组
nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
2 题目解析
输入是数组nums，输出是除nums[i]各元素的累乘结果组成的数组answer。
由于题目禁用除法，我们只能老老实实用乘法，而不能所有元素累乘然后除以对应下标。按照暴力求解，将除了下标的元素累乘，总共要进行n遍，平均时间复杂度为O(n^2)，不可行。
3 算法原理及代码实现
3.1 左右乘积列表
我们转换个思路，除去元素nums[i]其余元素累乘，等价于nums[i]左边的元素和右边的元素累乘。据此，我们初始化两个数组L和R。其中，L[0]=1，R[n-1]=1，n为nums的长度。我们执行如下步骤：
①初始化L和R
②对于L，
③对于R，
④
这样平均时间复杂度为O(n)，平均空间复杂度为O(n)。
进一步优化，我们观察发现，空间复杂度主要应为开辟了L和R而变得复杂，那我们能不能不要L和R呢？我们可以将原来的L直接用answer来代替，answer[i]代表i左侧所有元素的乘积。然后，用一个变量R跟踪右边元素的乘积，即，
。
这样，平均时间复杂度为O(n)，平均空间复杂度为O(1)。
C++代码实现
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n=nums.size();
int R=1;
vector<int> answer(n);
answer[0]=1;
for(int i=1;i<n;i++){
answer[i]=answer[i-1]*nums[i-1];
}
for(int i=n-1;i>=0;i--){
answer[i]*=R;
R*=nums[i];
}
return answer;
}
};Python代码实现
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n,R=len(nums),1
answer=[1]*n
for i in range(1,n):
answer[i]=answer[i-1]*nums[i-1]
for i in range(n-1,-1,-1):
answer[i]*=R
R*=nums[i]
return answer