文章目录
- 题目链接：
- 题目描述：
- 解法
- C++ 算法代码：
- 图解
题目链接：
238. 除自身以外数组的乘积
题目描述：
解法
暴力枚举：O(n2)
边枚举位置，边算乘积。
前缀和思想：
- 预处理前缀积和后缀积
f：前缀积数组 这里面f[i]表示：[0,i-1]区间所有元素的积
g：后缀积数组 这里面g[i]表示：[i+1,n-1]区间所有元素的积
f[i]=f[i-1]*nums[i-1]
g[i]=g[i+1]*nums[i+1]
-
使用
ret数组存储i，使得i=f[i]*g[i] -
注意细节问题，比如
i=0的时候i-1不存在以及
f[0]要设置为1，g[n-1]设置为1因为如果
f[0]=0，那么f[1]=0*nums[0]=0，后面就全0了
C++ 算法代码：
class Solution
{public:vector<int> productExceptSelf(vector<int>& nums) {// lprod 表示：[0, i - 1] 区间内所有元素的乘积// rprod 表示：[i + 1, n - 1] 区间内所有元素的乘积int n = nums.size();vector<int> lprod(n + 1), rprod(n + 1);lprod[0] = 1, rprod[n - 1] = 1;// 预处理前缀积以及后缀积for(int i = 1; i < n; i++)lprod[i] = lprod[i - 1] * nums[i - 1];for(int i = n - 2; i >= 0; i--)rprod[i] = rprod[i + 1] * nums[i + 1];// 处理结果数组vector<int> ret(n);for(int i = 0; i < n; i++)ret[i] = lprod[i] * rprod[i];return ret;}
};
图解
例如：nums = [1,2,3,4]
