给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2示例 2：
输入：nums = [1,2,3], k = 3
输出：2提示：
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
解题思路：前缀和 + 哈希表
首先看到连续子数组，我们会想到用滑动窗口来解决这道题，但其实这道题用滑动窗口的话只能暴力破解，因为这道题元素可能是负数或者为 0，那么此时如果使用滑动窗口的话，会遗漏中间的一些情况，这都是因为滑动窗口的指针不会回退的原因，但如果要回退的话，时间复杂度就比较高了，所以这道题无法使用滑动窗口来解决！
所以我们要换个思路，因为这道题也涉及到数组的连续和，所以可以考虑使用前缀和来解决这道题！
假设我们此时已经移动到了 i 位置处，那么我们要求就是从 [0, i] 区间达到目标值的子数组的个数。那么我们可以用一个数组 sum 来记录前缀和，即 sum[i] 表示从 [0, i] 区间上的元素和。
此时我们会发现，有可能我们要求的这个子数组不是从下标为 0 处开始的，但我们的 sum 数组表示的前缀和又是从下标为 0 处开始，所以我们得把问题进行转化一下！
最常见的转换方法，其实就是转变一下目标值对象，比如这里用当前所求的 sum[i] 即前缀和，减去目标值 k，最后得到的区间一定是从 0 开始的，如下图所示：
因为满足和为 k 的区间，一定最后是连着 i 位置的，所以一定是后半部分是连续的，那么我们只需要使用当前区间的总和 sum[i] 减去 k，得到的就是前半部分区间，那么就是从下标为 0 开始的！
也就是说，我们现在问题转化为求 [0, i] 区间内满足 sum[i] - k 的子数组的个数！
但是问题又来了，如果我们遍历到 i 位置处，然后再去查找 [0, i] 区间内满足 sum[i] - k 的子数组的个数的话，那这个时间复杂度貌似和暴力破解没什么区别呀，所以这里要使用哈希表，快速定位前面区间内一共有多少个满足要求的子数组，所以哈希表的结构我们设为 unordered_map<int, int>，前面的 int 表示目标值，后面的 int 表示该目标值出现的次数！
也就是说，每当我们遍历到 i 处之后，这时我们只需要通过哈希表，查看前面前缀和满足 sum[i] - k 的子数组有多少个即可，即查找 sum[sum[i] - k] 的个数！
此时就引入了几个细节问题：
- 哈希表键值对的插入时机
- 对于插入时机，我们是需要在遍历
i的时候再将键值对插入到哈希表中，而不能一开始进行预处理，将整个数组的键值对插入到哈希表中，因为我们在遍历的时候，是从前往后遍历，并且需要的只是[0, i]区间上的目标键值对，不能被后面的键值对干扰，所以必须是边走边插入！
- 对于插入时机，我们是需要在遍历
- 我们可以使用一个变量来代替前缀和数组
- 因为前缀和
sum[i]的求法是sum[i] = sum[i - 1] + nums[i]，那么其实我们只需要一个变量来作为当前的前缀和记录，即sum = sum + nums[i]，效果是一样的！
- 因为前缀和
- 区间元素目标值的特殊情况
- 有一种特殊情况，就是有可能
sum = k，即当前[0, i]的目标值要求是sum - k = 0，即整个区间[0, i]区间都是我们要求的，那我们去哈希表中查找sum - k的时候，即查找0的时候，此时我们需要的结果是1，所以我们要提前处理一下哈希表，让hash[0] = 1。
- 有一种特殊情况，就是有可能
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> hash;
hash[0] = 1; // 预处理
int sum = 0;
int ret = 0;
for(int i = 0; i < nums.size(); ++i)
{
sum += nums[i]; // 计算前缀和
if(hash.count(sum - k))
ret += hash[sum - k]; // 统计出现sum-k的个数
hash[sum]++;
}
return ret;
}
};