Subarray Sum Equals K

Start dumb: sum every subarray

Count the subarrays summing to k? Try them all: every start i, every end j, keep a running sum as j grows. That’s O(n²) subarray checks — workable for toy inputs, hopeless at LeetCode’s 2·10⁴ elements.

Find the bottleneck

Your first instinct might be a sliding window — but nums can hold negatives and zeros, so growing the window doesn’t reliably raise the sum and shrinking doesn’t reliably lower it. The window’s control signal is dead. What the brute force wastes is different: it recomputes sums over the same elements again and again, when every one of those sums is just a difference of two running totals.

The optimal shape

One pass, one map:

1. Seed the map with {0 → 1} — the empty prefix.
2. Absorb each element into the running prefix.
3. Look up prefix − k; every hit is a subarray ending here. Add the count.
4. Then record the current prefix in the map for future indices.

Each element is absorbed once with O(1) map work — O(n) time, O(n) space for the map. In the player below, the map in the state pane grows as the answer assembles; when a lookup hits, the matched subarray lights up in the array.

Watch it think

Step through the default, then stress the parts windows can’t handle: zeros (0,0 | 0 — count the three), cancelling negatives (-1,1 | 0), and the classic mixed case 3,4,7,2,-3,1,4,2 | 7.

1fun subarraySum(nums: IntArray, k: Int): Int {
2    val prefixCounts = HashMap<Int, Int>()
3    prefixCounts[0] = 1 // the empty prefix — drop it and subarrays starting at 0 vanish
4    var prefix = 0
5    var count = 0
6    for (num in nums) {
7        prefix += num
8        val need = prefix - k
9        count += prefixCounts.getOrDefault(need, 0)
10        prefixCounts[prefix] = prefixCounts.getOrDefault(prefix, 0) + 1
11    }
12    return count
13}