Subarray Sum Equals K

LeetCode 560 · View on LeetCode

Prefix sum + hash map. The math: a subarray nums[i..j] sums to k when prefix[j] - prefix[i] == k. Rearranged: at each position j, check if we've seen a prefix sum equal to currentSum - k. Each match means there's a subarray ending here that sums to k.

Why {0: 1}? It represents the empty prefix (sum before the array starts). Without it, you'd miss subarrays starting at index 0 where sum == k.

package main

import "fmt"

func subarraySum(nums []int, k int) int {
	count := 0
	sum := 0
	seen := map[int]int{0: 1} // empty prefix: sum of nothing = 0
	for _, n := range nums {
		sum += n            // prefix sum up to here
		count += seen[sum-k] // how many earlier prefixes give us a valid subarray?
		seen[sum]++         // record this prefix for future positions
	}
	return count
}

// Walkthrough: nums = [1, 1, 1], k = 2
//
//   seen = {0:1}
//
//   i=0: sum=1, need=1-2=-1, seen[-1]=0 → count=0, seen={0:1, 1:1}
//   i=1: sum=2, need=2-2= 0, seen[0] =1 → count=1, seen={0:1, 1:1, 2:1}
//   i=2: sum=3, need=3-2= 1, seen[1] =1 → count=2, seen={0:1, 1:1, 2:1, 3:1}
//
//   Answer: 2 → subarrays [1,1](index 0-1) and [1,1](index 1-2)

func main() {
	fmt.Println(subarraySum([]int{1, 1, 1}, 2))  // 2
	fmt.Println(subarraySum([]int{1, 2, 3}, 3))  // 2
	fmt.Println(subarraySum([]int{1, -1, 0}, 0)) // 3
}