LC560 - 和为K的子数组

package Substring

// 时间复杂度: O(n), 空间复杂度: O(n)
func subarraySum(nums []int, k int) int {
    nums = append([]int{0}, nums...)
    prefixSum := make([]int, len(nums))
    for i := 1; i < len(nums); i++ {
        prefixSum[i] = prefixSum[i-1] + nums[i]
    }
    // nums[i...j]累加和 = prefixSum[j] - prefixSum[i - 1]
    hashMap := make(map[int]int)
    hashMap[0] = 1
    result := 0
    for i := 1; i < len(nums); i++ {
        result += hashMap[prefixSum[i]-k]
        hashMap[prefixSum[i]]++
    }
    return result
}

前缀和+两数之和