前缀和——和为K的子数组

作者感觉本题稍稍有点难度，看了题解也思考了有一会TWT

显然，暴力我们是不可取的，但这里我们可以采取一种新的遍历数组形式，从后向前，也就是以i位置为结尾的所有子数组，这个子数组只统计i位置之前的。

然后，问题就转换成了，我们要找到以i位置为结尾的所有子数组，且在[0,i-1]内，有多少个前缀和为sum[i]-k,

‘

这里可能会有一个疑问，为什么和为k的数组都是以i位置为结尾的，就没有别的情况也符合比如下图

如果你对此有疑问，说明我们需要再看一下以i为结尾的所有数组为什么能有遍历所有数组的效果。如果我们正着看，就是0位置从前向后遍历，然后0开始的遍历完再从以1位置为开始的遍历，在我们本题中的遍历方法，无非就是把i作为了结尾，然后从右向左，也可以实现枚举所有子数组。

因此，如果上面的成立，一定在此之前就已经被统计过了。

还有一个细节，如果整个sum[i]=k怎么办？也就是说我们的sum[i]-k=0也算是成立的（前缀和为0）此时我们要定义一个hash，并令hash[0]=1；

最后，我们还要考虑一下每一次的前缀和什么时候放进表中，不能统计完就直接进，而是当移动一个位置时先判断是否有符合的再放入（防止重复）。

int Solution(vector<int> nums,int k)
{unordered_map<int,int>hash;hash[0]=1;int sum=0,ret=0;for(auto x:nums){sum+=x;if(hash.count(sum-k) ret+=hash[sum-k];hash[sum]++;//先判断再放入}return ret;
}