给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
进阶：
你可以在常数空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/product-of-array-except-self
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
方法1：分别构建前缀积、后缀积的矩阵
前缀积定义为：索引左侧的所有元素的乘积
后缀积定义为：索引右侧的所有元素的乘积
前缀积乘后缀积即为目标结果；
算法：
（1）初始化三个vector，res结果数组、c前缀积数组、d后缀积数组，并将c，d中的元素全部初始化为1
（2）使用两个for循环来填充c，d。
（3）c，d填充完毕后，索引i处的结果值为c[i]*d[i];
class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { if(nums.empty()) return {}; vector<int>res,c,d; c.resize(nums.size(),1); d.resize(nums.size(),1); int n = nums.size(); for(int i=1;i<n;i++) { c[i]=c[i-1]*nums[i-1]; d[n-1-i] = d[n-i]*nums[n-i]; } for(int i=0;i<n;i++) { res.push_back(c[i]*d[i]); } return res; } };
时间复杂度O(n),空间复杂度O(n)
方法二：
思路
尽管上面的方法已经能够很好的解决这个问题，但是空间复杂度并不为常数。
由于输出数组不算在空间复杂度内，那么我们可以将c 或 d 数组用输出数组来计算。先把输出数组当作 c数组来计算，然后再动态构造 d 数组得到结果。让我们来看看基于这个思想的算法。
（1）初始化res矩阵，对于给定索引i，res[i]代表i左侧所有数字的乘积
（2）与上面构造d矩阵不同，这里使用一个变量R动态构造右侧的后缀积，从后向前遍历res,计算最终结果为res[i]=res[i]*R,并更新R = R* num[i],R 代表索引右侧的后缀积
class Solution { public: vector<int> productExceptSelf(vector<int>& nums) { if(nums.empty()) return {}; vector<int>res; res.resize(nums.size(),1); int R=1; int n = nums.size(); for(int i=1;i<n;i++) { res[i]=res[i-1]*nums[i-1]; } for(int i=n-1;i>=0;i--) { res[i] = res[i] * R ; R = R * nums[i]; } return res; } };
原文：https://www.cnblogs.com/renzmin/p/13047000.html