今天我们来说一下刷题时经常用到的 前缀和 思想， 前缀和 和 滑动窗口 会经常用在求 子数组和子串 问题上，当我们遇到此类问题时，则应该首先想到此类解题方式，该文章会深入浅出描述前缀和，读完这个文章就会有 属于自己的解题框架 ，遇到此类问题时就能够轻松应对，我个人建议做题时不要背代码模板，应该自己进行总结，下次遇到时自然而然就能写出了。
下面我们先来了解一下什么是前缀和
前缀和其实我们很早之前就了解过的，我们求数列的和时，Sn = a1+a2+a3+...an; 此时Sn就是数列的前 n 项和 前缀和数组里保存的就是 前 n 项的和
我们通过前缀和数组保存前 n 位的和 presum[1] presum[2] presum[1]
例如我们需要获取 nums[2] 到 nums[4] 这个区间的和，我们则可以完全根据 presum 数组
好啦，我们已经了解了前缀和的解题思想了，我们可以通过下面这段代码得到我们的前缀和数组
好啦，我们开始实战吧。
leetcode 724. 寻找数组的中心索引题目描述
给定一个整数类型的数组 nums，请编写一个能够返回数组 “中心索引” 的方法。
我们是这样定义数组 中心索引 的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。
示例 1：
输入：nums = [1, 7, 3, 6, 5, 6] 输出：3
解释：索引 3 (nums[3] = 6) 的左侧数之和 (1 + 7 + 3 = 11)，与右侧数之和 (5 + 6 = 11) 相等。同时, 3 也是第一个符合要求的中心索引。
示例 2：
输入：nums = [1, 2, 3] 输出：-1
解释：数组中不存在满足此条件的中心索引。
解析
理解了我们前缀和的概念（不了解好像也可以做，这个题太简单了哈哈）。我们可以一下就能把这个题目做出来，先遍历一遍求出数组的和，然后第二次遍历时，直接进行对比左半部分和右半部分是否相同，如果相同则返回 true，不同则继续遍历。
leetcode 560. 和为K的子数组题目描述
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
暴力法
解析
我们先来用暴力法解决这个题目，很简单，一下就能 AC。
这个题目的题意很容易理解，就是让我们返回和为 k 的子数组的个数，所以我们直接利用双重循环解决该题，这个是很容易想到的。我们直接看代码吧。
好啦，既然我们已经知道如何求前缀和数组
我们分析上面的代码，发现该代码虽然用到了前缀和数组，但是对比暴力法并没有提升性能，时间复杂度仍为O(n^2)，空间复杂度却成了 O(n)。那我们有没有其他方法解决呢？
前缀和 + HashMap
了解这个方法前，我们先来看一下下面这段代码，保证你很熟悉
上面的这段代码是不是贼熟悉，没错就是那个快被我们做烂的两数之和。这一段代码就是用到了我们的前缀和+ HashMap 思想，那么我们如何通过这个方法来解决这个题目呢？
在上面的代码中，我们将数组的值和索引存入 map 中，当我们遍历到某一值 x 时，判断 map 中是否含有 target - x，即可。
其实我们现在这个题目和两数之和原理是一致的，只不过我们是将所有的前缀和该前缀和出现的次数存到了 map 里。下面我们来看一下代码的执行过程。
我们来拆解一下动图，可能有的同学会思考为什么我们只要查看是否含有 presum - k ，并获取到presum - k 出现的次数就行呢？见下图
因为我们此时 presum 已知，如果知道了presum - k 的个数，也就知道了 k 的个数。所以我们完全可以通过 presum - k的个数获得 k 的个数
好啦我们来看一下代码吧
做完这个题目，各位也可以去完成一下这个题目，两个题目几乎完全相同 leetcode 930. 和相同的二元子数组
leetcode1248. 统计「优美子数组」题目描述
给你一个整数数组 nums 和一个整数 k。
如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。
示例 1：
输入：nums = [1,1,2,1,1], k = 3 输出：2 解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2：
输入：nums = [2,4,6], k = 1 输出：0 解释：数列中不包含任何奇数，所以不存在优美子数组。
示例 3：
输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2 输出：16
如果上面那个题目我们完成了，这个题目做起来，分分钟的事，不信你去写一哈，百分百就整出来了，我们继续按上面的思想来解决。
前缀和 + HashMap
解析
上个题目我们是求和为 K 的子数组，这个题目是让我们求 恰好有 k 个奇数数字的连续子数组，这两个题几乎是一样的，上个题中我们将前缀区间的和保存到哈希表中，这个题目我们只需将前缀区间的奇数个数保存到区间内即可，只不过将 sum += x 改成了判断奇偶的语句，见下图。
我们来解析一下哈希表，key 代表的是含有 1 个奇数的前缀区间，value 代表这种子区间的个数，含有两个，也就是nums[0],nums[0,1].后面含义相同，那我们下面直接看代码吧，一下就能读懂。
但是也有一点不同，就是我们是统计奇数的个数 模拟 HashMap 索引来模拟 HashMap 的 key 值来模拟哈希表的 value 。下面我们直接看代码吧。
leetcode 974 和可被 K 整除的子数组
题目描述
给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。
示例：
输入：A = [4,5,0,-2,-3,1], K = 5 输出：7
解释：
有 7 个子数组满足其元素之和可被 K = 5 整除：[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
前缀和+HashMap
解析
我们在该文的第二题 和为K的子数组
我们需要找到满足，和为 K 的区间。我们此时 presum 找到 presum - k 区间的个数
我们在之前的例子中说到，presum[j+1] - presum[i] 可以得到 nums[i] + nums[i+1]+.... nums[j] [i,j]区间的和
那么我们想要判断区间 [i,j] 的和是否能整除 K，也就是上图中红色那一段是否能整除 K，那么我们只需判断
(presum[j+1] - presum[i] ) % k 是否等于 0 即可，
我们假设 (presum[j+1] - presum[i] ) % k == 0；则
presum[j+1] % k - presum[i] % k == 0;
presum[j +1] % k = presum[i] % k ;
我们 presum[j +1] % k 的值 key 是已知的，即是当前的 presum 和 k 的关系，所以我们只需要知道 presum[i] 和 presum[j+1] % k 含有相同余数 时 i 有几种情况
我们看到上面代码中有一段代码是这样的
这是为什么呢？不能直接用 presum % k 吗？
这是因为当我们 presum 为负数时，需要对其纠正
例如输入为 [-1,2,9],K = 2如果不对其纠正则会漏掉区间 [2] 此时 2 % 2 = 0，符合条件，但是不会被计数。
那么这个题目我们可不可以用数组，代替 map 呢？当然也是可以的，因为此时我们的哈希表存的是余数，余数最大也只不过是 K-1所以我们可以用固定长度 K 的数组来模拟哈希表。
leetcode 523 连续的子数组和题目描述
给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
示例 1：
输入：[23,2,4,6,7], k = 6 输出：True
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。
示例 2：
输入：[23,2,6,4,7], k = 6 输出：True
解释：[23,2,6,4,7]是大小为 5 的子数组，并且和为 42。
前缀和 + HashMap
这个题目算是对刚才那个题目的升级，前半部分是一样的，都是为了让你找到能被 K 整除的子数组，但是这里加了一个限制 子数组的大小至少为 2
此时我们 K = 6, presum % 6 = 4 也找到了相同余数的前缀子数组 [0,1] 但是我们此时指针指向为 2 下界为1
那我们有两个区间[0,1],[0,2]都满足 presum % 6 = 4，那我们哈希表中保存的下标应该是 1 还是 2 呢？我们保存的是1，如果我们保存的是较大的那个索引，则会出现下列情况，见下图。
此时，仍会显示不满足子区间长度至少为 2 的情况，仍会继续遍历，但是我们此时的 [2,3] 区间已经满足该情况
细节1：
细节2： 赋初值为 map.put(0,-1)。
视频解析
下面我们直接看代码吧，一下就能 整懂啦。
--end--
