560. Subarray Sum Equals K

Medium

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

• 1 <= nums.length <= 2 * 10^4

• -1000 <= nums[i] <= 1000

• -10^7 <= k <= 10^7

解題

func subarraySum(nums []int, k int) int {
    res, sum := 0, 0
    n := len(nums)

    m := make(map[int]int) //紀錄前綴和出現次數
    m[0] = 1
    for i := 0; i < n; i++ {
        sum += nums[i]
        res += m[sum - k]
        m[sum]++
    }

    return res
}