这几天都没有写Leetcode的总结，但是其实我也不是没有刷题，这几天主要写了两个内容的问题，一个部分动态规划，另外一个问题是前缀和。

动态规划：

零钱兑换、零钱兑换II、一和零

动态规划的总结我发在Leetcode上面了

https://leetcode-cn.com/problems/coin-change/solution/ling-qian-dui-huan-ling-qian-dui-huan-ii-gpd4/

前缀和：

连续的子数组和、和为K的子数组和、长度最小的子数组

连续的子数组和

这道题需要计算连续的子数组的和，而且这个和需要满足为k的倍数的特定条件。如果使用暴力方法的话，则需要使用O(n^2)。

我们可以利用前缀和提供的良好的性质来处理这个问题。

构建一个n+1长度的数组作为前缀和。遍历前缀和数组中的所有元素，如果两者对于K的余数相同，这两者构成的数组是题目需要的子数组。

在实际操作的过程中，因为题目要求数组的长度需要大于等于2。起始的index从1开始即可，但是由于计算前缀和的公式中是sum[j+1] - sum[i] = [i,j]之间数组的元素和。所以我们index从2开始。并且使用hashset存放取余之后的结果，如果出现重复，说明前面有一个元素下标为i满足要求。代码如下：

和为K的子数组

看到题目中要求是连续数组，则想到可以尝试前缀和。这道题没有上面对于数组长度的限制，长度为一也是可以的。以下面的例子为例，如果当前下标为j，指向前缀和是第一个出现的6，sum[j+1] - sum[i] == k成立，其实sum[j+1]输出的方法数依赖着sum[i]，所以我们需要存储每一个元素的方法数，并且最后的count需要加上sum[i]