前缀和专题
板子：
（占坑）
Leetcode 238. 除自身以外数组的乘积
优化前：使用前后缀数组记录
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> pre(n, 1), suf(n, 1), ans(n, 0);for(int i = 0; i < n; i ++)pre[i] = (i==0?1:pre[i - 1]) * nums[i];for(int i = n - 1; i >= 0; i --)suf[i] = (i==(n - 1)? 1 : suf[i + 1]) * nums[i];for(int i = 0; i < n; i ++)ans[i] = (i==0?1:pre[i - 1]) * (i==(n-1)?1:suf[i + 1]);return ans;}
};优化后：
先计算 pre，然后一边计算 suf，一边把 suf直接乘到 pre[i] 中。最后返回 pre。(注意：suf是从1开始累乘的)
题目说「输出数组不被视为额外空间」，所以该做法的空间复杂度为 O(1)。此外，这种做法比上面少遍历了一次。
class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> pre(n, 1);// 计算出前缀和数组for(int i = 1; i < n; i ++)pre[i] = pre[i - 1] * nums[i - 1];// 针对前缀和数组补上后缀计算部分即可int suf = 1;for(int i = n - 1; i >= 0; i --){pre[i] = pre[i] * suf;suf *= nums[i];}return pre;}
};