【前缀合】Leetcode 和为k的子数组

题目解析

560. 和为 K 的子数组

算法讲解

前面滑动窗口里面有一道题和这个题很相似，它是求出和为k的最短子数组的长度，但是这道题不能使用滑动窗口，因为虽然找到一段子数组的和等于k，但是这道题里面存在0和负数，可能这一段区间里面还有一段子数组也等于k
因此需要使用前缀和算法，我们求出以i位置为结尾的前缀和，在这一段区间中寻找有没有前缀和 - k的区间

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int>Hash;
        int sum = 0;
        int ret = 0;
        Hash[0]++;
        for(auto& n : nums)
        {
            sum += n;  //此处计算的就是以i位置为结尾的前缀和
            if(Hash.count(sum - k))ret += Hash[sum - k];  //寻找这一段区间有没出现sum - k)
            Hash[sum]++;
        }
        return ret;
    }
};