目录
27. 一维前缀和模板：
27.1 题目解析：
题目大家仔细的阅读一下，就可以很好的理解了。那么咱们主要来讲一下前缀和算法：就是可以快速求出数组中某一个连续的区间的的和。
27.2 算法思路：
算法就是使用前缀和去做。
那么这个图片上的什么意思呢？
好，通过看这个是不是就了解了第一张图片什么意思，就是创造了一个前缀和数组。然后前缀和数组如何求的呢？就是用到了第二张图片的第二个公式。
现在到了第二步，就是使用前缀和数组：
咱们要求一个区间，l与r之间的区间的和，是不是直接就可以使用前缀和数组相减不就可以了吗？
dp[l-1]是0到l-1内的和（因为咱们要求的是l到r的和，所以l也得算上）。
那么咱们再来思考一个问题：就是为什么下标要从1开始呢？其实呢，是因为避免处理边界情况，假设下标从0开始，那么：
dp[-1]不是就越界了嘛？以及还要令dp[0]=0才可以。否则，1-2区间内的和没法求。
等咱们后面学了动态规划，就知道这个是初始化：添加虚拟结点（辅助结点）。
27.3 代码演示：
int main() {
//1.输入数据
int n = 0; int q = 0;
cin >> n >> q;
vector<int> arr(n + 1);//增加n+1个位置，并初始化为0
for (int i = 1; i <= n; i++) cin >> arr[i];
//2.预处理前缀和数组
vector<long long>dp(n + 1);//使用long long 防止溢出
for (int i = 1; i <= n; i++) dp[i] = dp[i - 1] + arr[i];
//3.使用前缀和数组
int l = 0; int r = 0;
while (q--)
{
cin >> l >> r;
cout << dp[r] - dp[l - 1] << endl;
}
return 0;
}
由于题目说的是1~n内的数字，所以说for的范围就是<=n.
27.4 总结反思
到了后面，这种题做的多了，会发现路子其实都是一样的。
28. 二维前缀和模板：
28.1 题目解析：
题目也很好理解，就是在一维上再增加一维，就是二维。就可以了。这个有点像那个二维数组。
28.2 算法思路：
这个咱们还是使用前缀和来做。
1.预处理出来一个前缀和矩阵：
这个的求和方法有点类似于小学做的奥数题，就是求面积的。需要注意的是，本题中说的下标是从1开始的，所以说咱们的下标原数组与dp数组都是相同的下标，所以不需要纠结下标的问题。但要是下标从0开始，那么就需要好好的算一下dp后的下标了。 还有就是，如果说你实在理解不了这个下标为什么这么写，你可以随机举一个例子，然后自己带进去看一看不就出来了吗？
2.使用前缀和矩阵。
本题中人家也是下标从1开始的，很好办。还是老办法，要是实在想不明白，自己举个例子，使用下标往里面带一带，不就清楚了吗？那么咱们再来看一下如果说下标从0开始的，是怎么个计算方法：
其实博主的字比这个好看多了，只因为这是我自己的笔记，所以说我就随便写的（遵循一个自己能看懂就可以了）。
28.3 代码演示：
int main() {
int n = 0; int m = 0; int q = 0;
cin >> n >> m >> q;
vector<vector<int>> arr(n + 1, vector<int>(m + 1));//由于下标从1开始，所以要开n+1，m+1个空间
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> arr[i][j];
}
}
//创造前缀和数组
vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
}
}
//使用前缀和数组
int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
while (q--)
{
cin >> x1 >> y1 >> x2 >> y2;
cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
}
return 0;
}28.4 总结反思：
博主也是用了很长时间才把这个给搞清楚，这个我感觉还是挺容易混的。所以大家一定要好好的看看，
29 力扣 724.寻找数组的中心下标
29.1 题目解析：
题目的意思就是找到一个数字，使得这个数字的左面的和等于右面的和，并返回这个下标。不过要注意一下例如0 0 0 这样的是返回坐左边的那个下标就可以了。
29.2 算法思路;
1.解法一肯定就是暴力解法：一个一个的枚举，这还没完，枚举完之后，枚举了一个，加一遍左边，再加一遍右边，等等，这样算下来，时间复杂度就是O(n).
2.第二种算法思路就是使用前缀和去做，不过本题需要用到前缀和加上后缀和（其实就是特殊的前缀和）。
第一步就是创造好前缀和数组：
这个f[i-1]代表的是0到i-2这个范围内的和，然后再加上第i-1这个位置的数字，就是0到i-1这个区间内的和。而g[i+1]代表的是i+2到n-1范围内的和。
之后一个一个的再去枚举0~n-1内的所有的下标i，之后判断f[i]与g[i]是否相等即可。
但我们还需要注意一些边界问题：
f[0]=0.是因为左边没有元素了，根据题意，那不就是0嘛。以及g[n-1]=0.右边没有元素了，所以也为0.
f是从左向右填表，是因为f[i]依赖于 f[i-1].而g从右向左填表，是因为g[i]依赖于g[i+1].
29.3 代码演示：
int pivotIndex(vector<int>& nums) {
int n = nums.size();
vector<int> f(n), g(n);
//求前缀和数组以及后缀和数组
for (int i = 1; i < n; i++)//i从1开始，因为i=0的时候，和为0，并且这个是从左往右填表
f[i] = f[i - 1] + nums[i - 1];
for (int i = n - 2; i >= 0; i--)//0到n-1
g[i] = g[i + 1] + nums[i + 1];
for (int i = 0; i < n; i++)//由于要枚举中点，所以要再增加一个for循环
{
if (f[i] == g[i])
{
return i;
}
}
return -1;
}
int main()
{
vector<int> nums = { 1, 7, 3, 6, 5, 6 };
cout << pivotIndex(nums) << endl;
return 0;
}这里是0~n-1，所以说，i<n即可。又因为可以取到0，所以说下面的i>=0.
29.4 总结反思：
还差最后一个题，这类的做法做法的基本思路就总结出来了。
30. 力扣238.除自身外数组的乘积
30.1 题目解析：
题目很好理解，返回的数组，每一个下标的代表的那个位置，除了那个位置之外的其他地方相乘就是那个位置的值。并且还是整个数组都是这样的。说明，咱们需要再另外创建一个数组去存储才可以。
30.2 算法思路：
同样的还是使用前缀和去做，只不过这次不是前缀和，而是前缀积。
不就是除了那个位置之外的，前缀积乘上后缀积嘛？这个f[i],g[i]的公式的意义与上一题一样，这里我就不过多的阐释了。
那么咱们算完之后，要创建一个数组，去返回这个成积即可。并且，这个还得是for循环，否则，无法覆盖到每一个位置。
同样需要处理一下边界条件，这里不可以再设f[0]为0了，因为0乘以任何数都为0，那这还有啥意义？
30.3 代码演示：
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> f(n), g(n);
f[0] = g[n - 1] = 1;//细节处理
//预处理一下前缀和数组以及后缀和数组
for (int i = 1; i < n; i++)
f[i] = f[i - 1] * nums[i - 1];
for (int i = n - 2; i >= 0; i--)
g[i] = g[i + 1] * nums[i + 1];
//使用前缀和数组以及后缀和数组
vector<int> outcome(n);
for (int i = 0; i < n; i++)
{
outcome[i] = f[i] * g[i];
}
return outcome;
}
int main()
{
vector<int> nums = { 1,2,3,4 };
vector<int> outcome = productExceptSelf(nums);
for (auto& e : outcome)
{
cout << e << "";
}
cout << endl;
return 0;
}由于这次也是使用的0~n-1范围内的数字。所以for的范围也是那些。
30.4 总结反思：
那么咱们就来说明一下这类题目的做法，相信从前面几道题，大家已经看出来是怎么个办法了。就是先分析题目，找出方程式（创建前缀和数组），之后使用前缀和数组，算出结果。最重要的是最后要处理一下边界条件，基本都是这样的。边界条件基本就是最前面以及最后面。
31.力扣 560.和为k的子数组
31.1 题目解析：
其实就是寻找子数组，那么一看到子数组，是不是就会想到咱们之前讲的双指针（滑动窗口），但其实这道题不可以使用。因为这道题包含0以及负数，咱们直到，滑动窗口，滑动的窗口里面不可以包含负数，否则就不可以使用。
31.2 算法思路：
那么既然滑动窗口不可以使用，咱们就是用前缀和加上哈希表。
这道题咱们是不是可以转化为求sum[i]-k？是的，可以这么转化的。
不过这里需要使用到哈希表。
、
上面是一些细节问题，大家看一下，深入理解一下。
31.3 代码演示：
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> hash; // 统计前缀和出现的次数
hash[0] = 1;
int sum = 0, ret = 0;
for (auto x : nums) {
sum += x; // 计算当前位置的前缀和
if (hash.count(sum - k))
ret += hash[sum - k]; // 统计个数
hash[sum]++;
}
return ret;
}
int main()
{
vector<int> nums = { 1,1,1 };
int k = 2;
cout << subarraySum(nums, k) << endl;
return 0;
}31.4 总结反思：
前缀和模板的题呢，还有3道，那么咱们明天再一起讲完。其实最基本的做题方法，今天已经传授给大家了，大家好好的参悟。
本篇完...................