560. 和为K的子数组
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]
/*
我们可以基于方法一利用数据结构进行进一步的优化，我们知道方法一的瓶颈在于对每个 ii，我们需要枚举所有的 jj 来判断是否符合条件，这一步是否可以优化呢？答案是可以的。
我们定义preli为0..2]里所有数的和，则prei可以由preli- 1] 递推而来，即:
pre[i]= pre[i- 1] + nums[i]
那么[j..i] 这个子数组和为k」这个条件我们可以转化为
pre[i]- pre[j- 1]==k
简单移项可得符合条件的下标j需要满足
pre[j- 1]== pre[i] - k:
所以我们考虑以i结尾的和为ke的连续子数组个数时只要统计有多少个前缀和为pre[i]- k的pre[j]即可。我们建立哈希
表mp,以和为键,出现次数为对应的值,记录pre[i]出现的次数,从左往右边更新mp边计算答案,那么以i结尾的答
案mp[pre[]一k]即可在0(1)时间内得到。后的答案即为所有下标结尾的和为k的子数组个数之和。
需要注意的是，从左往右边更新边计算的时候已经保证了mp[pre[i] - k] 里记录的pre[j] 的下标范围是0≤j≤i.同
时，由于pre[i] 的计算只与前一项的答案有关,因此我们可以不用建立pre数组，直接用pre量来记录pre[i - 1] 的答
案即可。
*/
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
map<int,int> mp;
int ret = 0;
int ans = 0;
mp[0]=1;
for(int i = 0;i<n;i++){
ans+=nums[i];
if(mp.find(ans-k)!=mp.end()){
ret+=mp[ans-k];
}
mp[ans]++;
}
return ret;
}
};
