算法4：前缀和（上）

一维前缀和

二维前缀和

寻找数组的中心下标

class Solution {
public:int pivotIndex(vector<int>& nums) {int n = nums.size();vector<int> f(n), g(n);f[0] = nums[0];g[n - 1] = nums[n - 1];for (int i = 1; i < n; ++i) {f[i] = f[i - 1] + nums[i];g[n - 1 - i] = g[n - i] + nums[n - 1 - i];}for (int i = 0; i < n; ++i) {if (f[i] == g[i])return i;}return -1;}
};

---

除自身以外数组的乘积

class Solution {
public:vector<int> productExceptSelf(vector<int>& nums) {int n = nums.size();vector<int> f(n), g(n);f[0] = nums[0];g[n - 1] = nums[n - 1];for (int i = 1; i < n; ++i) {f[i] = f[i - 1] * nums[i];g[n - 1 - i] = g[n - i] * nums[n - 1 - i];}vector<int> res(n);res[0] = g[1];res[n - 1] = f[n - 2];for (int i = 1; i < n - 1; ++i) {res[i] = f[i - 1] * g[i + 1];}return res;}
};