Leetcode: Subarray Sum Equals K

Subarray Sum Equals K

Similar Problems:

• Minimum Size Subarray Sum
• Binary Subarrays With Sum
• CheatSheet: Leetcode For Code Interview
• Tag: #hashmap, #subarray, #presum

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1:

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

Note:

1. The length of the array is in range [1, 20,000].
2. The range of numbers in the array is [-1000, 1000] and the range of the integer k is [-1e7, 1e7].

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

// 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
}