Subarray Sum Equals K

1. Problem Description

Given an integer array and an integer k, find the number of contiguous subarrays whose sum equals k.

2. Approach

1. Approach 1
   • Brute force
   • Use two nested loops to compute the sum
2. Prefix sum

3. Implementation

3.1. Brute Force

package main

func subarraySum(nums []int, k int) int {
	count := 0
	for i := 0; i < len(nums); i++ {
		sum := 0
		for j := i; j < len(nums); j++ {
			sum += nums[j]
			if sum == k {
				count++
			}
		}
	}
	
	return count
}

3.2. Prefix Sum

func subarraySum(nums []int, k int) int {
	// key is a prefix sum, value is the number of occurrences of that prefix sum
	preSumCount := make(map[int]int, 0)
	preSumCount[0] = 1
	preSum := 0
	count := 0
	for _, num := range nums {
		preSum += num
		count += preSumCount[preSum-k]
		preSumCount[preSum] += 1
	}
	return count
}

4. References

• 560. Subarray Sum Equals K - LeetCode
• Brute Force, Prefix Sum, and Prefix Sum Optimization (Java) - Subarray Sum Equals K - LeetCode