Leetcode.560.和为k的子数组
原题链接：链接
代码：
class Solution {
public:int subarraySum(vector<int>& nums, int k) {int n = nums.size();vector<int> vec(n+1);for(int i = 1;i<=n;i++){vec[i] = vec[i-1]+nums[i-1];}unordered_map<int,int> hash;hash[0] = 1;int res = 0;for(int i = 1;i<=n;i++){hash[vec[i]]++;res+=hash[vec[i]-k];}return res;}
};思路：
因为数组中元素是乱序的，所以用滑动窗口做不了，他要的是连续的子数组，是连续的，而前缀和之间的差正好是一段区间的和，满足这一要求，所以用前缀和；
至于要返回这种区间的个数，相当于在找前缀和与k之间的差值，能找到就加到答案中去，找不到该前缀和自己就成为被别人找的对象，所以可以用哈希表；
其他：
hash[vec[i]]++;
res+=hash[vec[i]-k];
这两行代码不可以交换顺序，否则出现下述这种样例过不了：
nums[] = {3}; k=0;
如果写反了，就会先把3放进hash中，那么结果就是3-0=3，肯定能在hash中找到这样的元素，与题目要求相悖。总之，k=0的样例都不容易通过；
参考：
链接