Subarray Sum Equals K

Problem

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

Key Insight

If we have a prefix sum at index j and another prefix sum at index i (where i < j), then:

sum of subarray [i+1, j] = prefix[j] - prefix[i]

So if prefix[j] - prefix[i] = k, then we found a valid subarray!

Rearranging: prefix[i] = prefix[j] - k

This means: At each position j, we ask “how many previous prefix sums equal curr - k?”

Approach

1. Iterate through the array, keeping a running prefix sum (curr)
2. At each position, check if curr - k exists in the cache
3. If it exists, the frequency tells us how many subarrays ending at the current position sum to k
4. Add the current prefix sum to the cache

The cache stores “how many times have we seen this prefix sum before?” — and that count directly translates to the number of valid subarrays.

Walkthrough

Let’s trace through nums = [1, 1, 1], k = 2:

nums:      [1, 1, 1]
indices:    0  1  2

prefix sums:
  prefix[0] = 1
  prefix[1] = 2
  prefix[2] = 3

Initialize: m = {0: 1}, curr = 0, count = 0

The map stores: {prefix_sum: how many times we've seen it}
We start with {0: 1} to represent the empty prefix (before index 0).

Index 0: nums[0] = 1

curr = 0 + 1 = 1
Looking for: curr - k = 1 - 2 = -1
Is -1 in map? NO
count stays 0

Add curr to map: m = {0: 1, 1: 1}

Index 1: nums[1] = 1

curr = 1 + 1 = 2
Looking for: curr - k = 2 - 2 = 0
Is 0 in map? YES, with frequency 1
count = 0 + 1 = 1

Why? We found a prefix sum of 0 (the empty prefix before the array).
  sum[0..1] = prefix[1] - 0 = 2 - 0 = 2 = k
  Subarray found: [1, 1] (indices 0-1)

Add curr to map: m = {0: 1, 1: 1, 2: 1}

Index 2: nums[2] = 1

curr = 2 + 1 = 3
Looking for: curr - k = 3 - 2 = 1
Is 1 in map? YES, with frequency 1
count = 1 + 1 = 2

Why? We found prefix[0] = 1.
  sum[1..2] = prefix[2] - prefix[0] = 3 - 1 = 2 = k
  Subarray found: [1, 1] (indices 1-2)

Add curr to map: m = {0: 1, 1: 1, 2: 1, 3: 1}

Result: count = 2

Why Frequency Matters

Let’s trace nums = [0, 0, 0], k = 0:

Initialize: m = {0: 1}, curr = 0, count = 0

Index 0: nums[0] = 0

curr = 0 + 0 = 0
Looking for: curr - k = 0 - 0 = 0
Is 0 in map? YES, freq = 1
count = 0 + 1 = 1   -> found [0] (indices 0-0)

Update map: m = {0: 2}  (now we've seen prefix sum 0 twice)

Index 1: nums[1] = 0

curr = 0 + 0 = 0
Looking for: 0 - 0 = 0
Is 0 in map? YES, freq = 2
count = 1 + 2 = 3   -> found [0] (index 1), and [0, 0] (indices 0-1)

Update map: m = {0: 3}

Index 2: nums[2] = 0

curr = 0 + 0 = 0
Looking for: 0 - 0 = 0
Is 0 in map? YES, freq = 3
count = 3 + 3 = 6   -> found [0] (index 2), [0, 0] (indices 1-2), [0, 0, 0] (indices 0-2)

Update map: m = {0: 4}

Result: count = 6

Solution

def solution(nums: list[int], k: int) -> int:
    m = {0: 1}      # empty prefix has sum 0, seen once
    curr = 0        # running prefix sum
    count = 0

    for num in nums:
        curr += num

        # How many previous prefixes give us a valid subarray?
        if curr - k in m:
            count += m[curr - k]

        # Record this prefix sum
        m[curr] = m.get(curr, 0) + 1

    return count

Complexity

• Time: O(n) - single pass through the array
• Space: O(n) - hash map can store up to n distinct prefix sums