Leetcode：前缀和系列

前缀和的精华就是需要一个额外的字典的帮助，不同的题中字典的key以及key对应的value所有不同：

• 情况1：key就是前缀和，value是前缀和出现的次数（最经常的情况，也就是中等题爱出的，往往题目中说求个数）
• 情况2：key是前缀和，value是位置的indx（这种情况下，往往题目是求长度）
• 情况3：key是跟前缀和有关的值

关于字典dicts的初始化问题：

• 如果求次数，那么dicts[0] = 1
• 如果求长度，那么dicts[0] = -1

尤其需要说明，前缀和一般适用于求和的情况，对于求乘积的情况要非常小心， 因为乘积的相乘后的符号会发生改变，例如：

152. 乘积最大子数组（采用动态规划）

713. 乘积小于 K 的子数组（采用双指针）

我从简单到困难梳理一下

类型1：一维数组情况下
（1）最基本的题，适合前缀和的入门：

• 560. 和为 K 的子数组（本题是求数组中和为 k 的连续子数组的个数，因此对应与前面所述的情况1）
• 930. 和相同的二元子数组（本题基本与上面一样）

• 525. 连续数组（本题是在930的基础上，变为求长度，对应于前面所述的情况2）

（2）进阶版

• 974. 和可被 K 整除的子数组（本题虽然是求除法，但是是求和能够被K整除的子数组的个数，因此是可以用前缀和的。本题是经典的情况3了，字典的key不再是前缀和，而是做了一个转换，储存余数）
• 523. 连续的子数组和（本题要求：所求子数组大小至少为 2，并且按要求和是为 k 的倍数，问是否存在，返回True or False，可以看到与974基本上一样，属于经典的情况3了。但是与974不同的是，对子数组的长度做了限制，因此key对应的value就不是个数，而是index，用于求是否满足长度大于2）

• 1248. 统计「优美子数组」

类型2：二维矩阵
1、304. 二维区域和检索 - 矩阵不可变
2、1314. 矩阵区域和
3、1074. 元素和为目标值的子矩阵数量
4、面试题 17.24. 最大子矩阵
5、363. 矩形区域不超过 K 的最大数值和

类型3：二叉树系列

437. 路径总和 III