LeetCode: Subarray Sum Equals K

## https://code.dennyzhang.com/subarray-sum-equals-k
## Basic Ideas: presum + hashmap
##
## Complexity: Time O(n), Space O(n)
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # value -> count
        freqs = collections.defaultdict(int)
        freqs[0] = 1
        n = len(nums)
        res, presum = 0, 0
        for i in range(n):
            presum += nums[i]
            res += freqs[presum-k]
            freqs[presum] += 1
        return res

// https://code.dennyzhang.com/subarray-sum-equals-k
// Basic Ideas: Presum + Dynamic Programming
//     Count how many subarray ends with current item
// Complexity: Time O(n), Space (n)
func subarraySum(nums []int, k int) int {
    res, preSum := 0, 0
    h := map[int]int{0: 1}
    for _, v := range nums {
       preSum += v
       res += h[preSum - k]
       h[preSum]++
    }
    return res
}