前缀和的主要作用就是求解数组中某一个连续区间中元素的和,重点在与前缀表的计算
-
前缀和模板题 前缀表的计算方式和对应的区间和的计算方式如下: $$ 前缀表: prefix[0] = 0
prefix[i + 1] = prefix[i] + nums[i] $$ 利用前缀表计算区间和的方式如下: $$ prefix[right + 1] = \sum_{i = 0}^{right} nums[i] $$ $$ prefix[left] = \sum_{i = 0}^{left - 1} nums[i] $$ 所以把两个式子相减就可以得到: $$ \sum_{i = left}^{right} nums[i] = prefix[right + 1] - prefix[left] $$
-
和为k的子数列 首先还是利用递推公式得到前缀表,之后在遍历的过程中利用哈希表记录前缀表中数字出现的个数,如果要求子串和为
k也就是: $$ prefix[j + 1] - prefix[i] = k $$ 可以转换为: $$ prefix[i] = prefix[j + 1] - k $$ 所以遍历到prefix[j + 1]的时候只需要求解prefix[j + 1] -k的个数即可,所以需要在遍历的过程中记录,这一个题目与两数之和类似,只是两数之和不需要几次次数,这里需要记录次数(所以两数之和可以使用unordered_set但是这里不可以)