560. 和为 K 的子数组 - 力扣（LeetCode）

因为是判断子数组的和 + 要返回 == k  的次数，所以

解法：前缀和 + 哈希表

提出一个概念：以下标i为结尾的所有子数组

那要找出所有和 == k的子数组 就相当于：找出所有值为dp[i] - k的子数组。

 dp[i] - k就是一段区间的前置和了，只要把所有以下标i为结尾的所有子数组的前缀和丢到哈希表中，最后返回 dp[i] - k (前提：要存在)出现的次数即可。

细节

1.前缀和什么时候丢入哈希表？

因为放进去的是前缀和，放[0,i]的话，到了[0,i+1]就会重复，所以到i下标时，先放入[0,i-1]的前缀和，再加入自己。(dp[i])

2.不用真的创建一个前缀和数组

dp[i] = sum + nums[i]  ，所以只需要一个sum代表前一次的前缀和，每次算完前缀和，把sum更新就行了。

3.如果到自己的前缀和是k呢？(dp[i] == k)

那范围就是：[0,-1]，显然不行，所以默认让hash[0] = 1

class Solution 
{
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        unordered_map<int,int> hash;
        hash[0] = 1;
        int sum = 0,count = 0;
        for(auto e : nums)
        {
            sum += e;
            if(hash.count(sum-k))
                count += hash[sum - k];
            //存完[0,i-1]后，再存自己
            hash[sum]++;

        }
        return count;


    }
};