560. Subarray Sum Equals K

Problem

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

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 * 104
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

Problem Summary

Given an integer array nums and an integer k, count and return the number of continuous subarrays in the array whose sum is k ****.

Solution Ideas

• This problem cannot be solved with a sliding window. Because nums[i] may be negative.
• The prefix sum approach can solve this problem, but the time complexity is a bit high, O(n^2). Consider optimizing the time complexity.
• The problem asks us to find the total number of subarrays whose continuous interval sum is k, that is, the sum within the interval [i,j] is K ⇒ prefixSum[j] - prefixSum[i-1] == k. So prefixSum[j] == k - prefixSum[i-1]. After this transformation, the problem becomes similar to A + B = K. Use the optimization idea from LeetCode Problem 1. Use a map to store accumulated results. After this optimization, the time complexity is O(n).

Code

package leetcode

func subarraySum(nums []int, k int) int {
	count, pre := 0, 0
	m := map[int]int{}
	m[0] = 1
	for i := 0; i < len(nums); i++ {
		pre += nums[i]
		if _, ok := m[pre-k]; ok {
			count += m[pre-k]
		}
		m[pre] += 1
	}
	return count
}