560.和为 K 的子数组

题目描述

思路 and Swift 题解

刚看到这道题目会把它当作一道滑动窗口的模版题，但由于数组当中可能存在负数，窗口当中的子数组和并不是单调递增的，因此不能使用滑动窗口的思路来解决这道题。

题目要求“和为 K 的子数组”，也就是求数组当中子数组的和，我们自然可以想到使用“前缀和”来对子数组的和进行表示。实际上，我们可以使用一个字典来统计某个前缀和的状态出现了多少次。设表示前缀和的变量为pref（显然我们不需要使用一个数组来存储每个位置的前缀和），如果pref- k已经出现过，那么统计其出现过的次数，将其累加到答案ans当中。对于本次累加后的前缀和，我们在字典当中记录一次前缀和的状态。

完整的 Swift 题解是：

class Solution {
    func subarraySum(_ nums: [Int], _ k: Int) -> Int {
        var pref = 0
        var mp = [Int: Int]()
        mp[0] = 1

        var ans = 0
        for num in nums {
            pref += num
            if let cnt = mp[pref - k] {
                ans += cnt
            }
            mp[pref, default: 0] += 1
        }

        return ans
    }
}