【力扣】238.除自身以外数组的乘积

AC截图

题目

思路

前缀积

前缀积指的是对于一个给定的数组arr，构建一个新的数组prefixProduct，其中prefixProduct[i]表示原数组从第一个元素到第i个元素（包括i）的所有元素的乘积。形式化来说：

• prefixProduct[0] = arr[0]
• 对于i > 0，prefixProduct[i] = arr[0] * arr[1] * ... * arr[i]

通过这种方式，你可以快速获取数组任意位置之前（包括当前位置）所有元素的乘积。

后缀积

类似地，后缀积是指对于给定数组arr，构建另一个数组suffixProduct，其中suffixProduct[i]表示原数组从最后一个元素到第i个元素（包括i）的所有元素的乘积。形式化来说：

• suffixProduct[n-1] = arr[n-1]，其中n是数组的长度。
• 对于i < n-1，suffixProduct[i] = arr[n-1] * arr[n-2] * ... * arr[i]

这样就可以迅速查询数组中任意位置之后（包括当前位置）所有元素的乘积。

本题可以根据题目要求，稍微修改一下，让前缀积和后缀积并不包含元素本身。

代码

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int len=nums.size();vector<int> res(len,1);int pre=1;int suf=1;for(int i=0;i<len;i++){res[i] *= pre;pre *= nums[i];}for(int j=len-1;j>=0;j--){res[j] *= suf;suf *= nums[j];}return res;}
};