下载掌阅APP，畅读海量书库
立即打开
若给定一个整数数组和一个整数 K ，则要如何找到和等于 K 的连续子数组的总数？举例如下。
输入：nums=[1，1，1]， K =2
输出：2
思路：此题考查哈希表的应用，初始化和为0的值为1，然后不断得到前缀和，减去 K 之后，看这个值是否存在，如果存在，则相加。注意：这里可能有负数，另外需要不断把前缀和放入哈希表中。
对于第一个元素1，前缀和为1，我们检测-1=1-2是否在字典中，如果在，则把其个数加入到最后的结果，同时更新前缀和为1的个数，记presum[1]=1。
对于第二个元素1，此时前缀和为2，检测0是否在字典中。因为我们初始化前缀和为0的值为1，所以此时res=1，其中res为和等于 K 的连续子数组的个数。同时更新前缀和为2的个数，记presum[2]=1。
对于第三个元素1，此时前缀和为3，我们检测1是否在字典中，因为presum[1]=1，此时res=2，同时更新前缀和为2的个数，presum[2]=1。
示例代码如下。
代码清单6-8 找到和等于 K 的连续子数组的总数
该方法的时间复杂度为 O （ n ），空间复杂度为 O （ n ）。
延展思考：如果数组中全是正数，可以利用双指针的方法求解。示例代码如下。
代码清单6-9 利用双指针的方法进行数组求和
该方法的时间复杂度为 O （ n ），空间复杂度为 O （1）。