和为K的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
提示：
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7
思路
看题目给的数据范围，枚举在数据较大时肯定会超时，枚举思路就是考虑以 i 结尾的和为 k 的连续子数组个数。这里只给出枚举代码（枚举思路较简单）
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int ans = 0;
for (int i = 0; i < nums.size(); ++i) {
int sum = 0;
for (int j = i; j >= 0; --j) {
sum += nums[j];
if (sum == k) ans++;
}
}
return ans;
}
};
正解（前缀和+哈希表）
由于枚举肯定会超时，所以要对其进行优化。我们可以通过前缀和尝试减少时间复杂度，定义 pre[i] 表示 nums 数组中前 i 个元素的和，那么 pre[i] = pre[i - 1] + nums[i]。
于是乎对于子数组[j…i]的和为k这个条件可以转化为pre[i] - pre[j - 1] == k。
经过简单移项后可得符合条件的下标 j 需要满足条件：pre[j - 1] == pre[i] - k
所以考虑以 i 结尾的和为 k 的子数组个数时，只需要统计有多少个前缀和为
pre[i] - k 的 pre[j] 即可。因为 j 在 i 之前，第一想法就是每次移动 i 时，需要从头往 i 遍历一次来看有没有满足条件的 pre[j]，但这一定会增加复杂度，所以我们可以通过哈希表来进行优化，以和为键，该和出现的次数为值，最后查找的时候就能在O(1)的时间内得到答案。代码如下
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int, int> mp;
mp[0] = 1; // 和为0出现了1次
int ans = 0, pre = 0;
for (auto& x : nums) { // 遍历数组（移动i）
pre += x; // 记录前缀和
if (mp.find(pre - k) != mp.end()) {
ans += mp[pre - k]; // 找到了一组[j, i]子数组
}
mp[pre]++; // 当前前缀和出现次数+1
}
return ans;
}
};
