【前缀和】560 和为k的子数组
题目
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
分析
- 暴力优化：固定左边界，移动右边界
代码实现
分析
【j…i】子数组和为k等价于pre[i]−pre[j−1]==k。即pre[j−1]==pre[i]−k。即考虑以i结尾的和为k的连续子数组时，只需要统计有多少个前缀和为pre[i]-k的pre[j]即可。因为prej是从第一个开始计算的。如此方便计算。因此建立哈希表，以和为键，出现次数为值。
注意：哈希表中是储存（sum，v）和（sum-k，v）的。把这两个变量的值都存在了哈希表中。找的是后者。