和为K的子数组链接
目录
第一步：了解题意编辑
第二步：算法原理
第三步：代码
第一步：了解题意
数组中和为k的连续子数组，我们主要关注的是连续的， 比如[1,1,1],和为2的子数组有俩个，比如第一个1和第二个1，还有第二个1和第三个1，都是属于俩种不同的情况。
比如[1,2,3],1+2=3属于一组，3也属于一组，所以有俩组。
我们可以认为
- sum-k=0,相当于sum=k属于一种情况，1+2=sum=3
- 还有一种情况是 sum-x=k,我们看到1+2+3=sum=6，x=3的时候，sum-x=k=3，我们也可以认为是满足情况的 （就是除去最后一个数前面的区间）
第二步：算法原理
-
解法1：暴力法，时间复杂度为O（n^2）
双循环，求出所有子数组的和，记录等于k的次数
- 解法2：哈希表，时间复杂度O(n)
首先思考暴力法的计算过程，我们会发现暴力法中存在很多重复计算的过程。例如我们计算数组nums[0]+nums[1]+nums[2]时，nums[1]+nums[2]被算了一次，当第二次循环计算nums[1]+nums[2]的时候，它又被计算了一次。所以，如果想要减少算法的时间复杂度，我们需要考虑如何减少重复计算。
因为数组的个数有限，所以计算出所有的累加和时间为O(n),我们用一个HashMap记录sum[],其中key为sum[i]，value为sum[i]出现的次数。若存在sum-k=x，x对应的value值为ret，则代表这种情况下有ret个子数组和为k。依次累加x1、x2...最终求出总个数。
步骤就是我们拿[1,1,1]来做说明
- sum=1 sum-k!=0 就不记入hash中，然后我们将hash[sum]++，就将sum=1存入hash表中
- sum=1+1=2 sum-k=0 记入hash中，ret++，然后就将hash[sum]++ ,就将sum=2存入hash中
- sum=1+1+1=3 sum-k=1 此时sum-k=1在hash表中出现过，ret++，然后就将hash[sum]++,将sum=3存入hash表中
我们疑惑的是为什么sum-k=1也ret++，因为我们上面说过了，sum-k=1,其实就是sum-1=k,如果前面存在sum=1的话，剩下的区间区间和等于k。
假如说sum-k等于前面出现过的某个前缀和的话，那么sum减去x其实就是减去了前面的一个区间此时剩下的这个区间的和就等于k。
当sum-k=1的时候说明sum减去前缀和为1的区间剩下的区间的和等于k，对应在这个111上就是sum减去第一个1之后剩下的区间加起来等于k。
也就是我上述说的俩种情况。第一种情况就是累加碰到sum[i]=k的那么就满足，第二种情况就是加到某个值之和之后我们减去k剩下的区间和是曾经累加的和，那么我们就也ret++。
这就得运用到hash表了，记录每次sum的值。
第三步：代码
class Solution {
public:
int subarraySum(vector<int>& nums, int k) {
unordered_map<int,int>hash;//统计前缀和出现的次数
hash[0]=1; //下标为0存入1，如果后面的sum-k==0，那么就加对应的值
//hash[0]=1 <0,1>绑定，前面的0代表sum-k=0，后面的1代表次数
int sum=0,ret=0;
for(auto x:nums)
{
sum+=x;//前缀和
if(hash.count(sum-k)) ret+=hash[sum-k];//统计个数
//（sum-k==0或者sum-k==曾经出现的前缀和_)
hash[sum]++;//将当前的前缀和留在hash中
}
return ret;
}
};
