本文主要是介绍力扣hot100：560.和为K的子数组（前缀和+哈希表），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
分析：
这个题目乍一看，数据大小用暴力解法大概率会超时，可能想用双指针，但是问题出现在 可能存在负数，也就是说即使是找到了一个答案，后面也可能存在负数和正数抵消，又是答案，因此不太行。
那如何想到前缀和的呢？ （我做的时候只能说灵光乍现，我也记不起来怎么想到的）
也许是因为，这里相当于是求 和为k的区间 个数，能快速求出区间和的就是前缀和了，拿到前缀和之后，对于任何一个sum[i]（0~i的和），如何求得sum[i]-sum[j]=k？实际上我们发现 值sum[j] 是确定的！因此我们可以用哈希表保存之前 前缀和为sum[j]的值的个数，并且这个哈希表只随着遍历进行保存（即对于每一个sum[i] 只会保存sum[i]之前的 前缀和）。
前缀和+哈希表
class Solution {
public:int subarraySum(vector<int>& nums, int k) {//前缀和+双指针vector<int> sum(nums.size());unordered_map<int,int> hmap;hmap[0]=1;//总和为0的情况 不加入元素时就有一种情况。long long ans=0;for(int i=0;i<nums.size();++i){if(i==0) sum[i]=nums[i];else sum[i]=sum[i-1]+nums[i];if(hmap.find(sum[i]-k)!=hmap.end()){//查看sum[i]-k在之前出现过没，如果出现过，则答案包含这个ans+=hmap[sum[i]-k];//sum[i]-sum[j]=k;}hmap[sum[i]]+=1;}return ans;}
};空间优化：
class Solution {
public:int subarraySum(vector<int>& nums, int k) {//前缀和+双指针int sum=0;unordered_map<int,int> hmap;hmap[0]=1;//总和为0的情况 一开始就有long long ans=0;for(int i=0;i<nums.size();++i){sum+=nums[i];if(hmap.find(sum-k)!=hmap.end()){//查看k-sum[i]在之前出现过没，如果出现过，则答案包含这个ans+=hmap[sum-k];//sum[i]-sum[j]=k;}hmap[sum]+=1;}return ans;}
};这篇关于力扣hot100：560.和为K的子数组（前缀和+哈希表）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
