Subarray Sum Equals K

Accumulate from every start

Choose each possible starting position. From there, extend the ending position one step at a time and carry the current sum forward. Every time that sum equals k, you've found one more slice.

def subarray_sum(nums: list[int], k: int) -> int:
    total = 0
    for start in range(len(nums)):
        current = 0
        for end in range(start, len(nums)):
            current += nums[end]
            if current == k:
                total += 1
    return total

Time O(n²) — there are about n²/2 start/end pairs. Space O(1).

Negative values are why you can't stop when current passes k: a later negative number can pull it back down.

Prefix-sum frequencies

A prefix sum is the total from the beginning of the array through one position. Suppose the current prefix sum is running. A slice ending here sums to k exactly when an earlier prefix sum equals running - k:

running - earlier = k

So you don't need the earlier positions themselves. You need a frequency map that tells you how many times each earlier prefix sum occurred. Add that frequency to the answer, then record the current sum for future positions.

def subarray_sum(nums: list[int], k: int) -> int:
    frequencies: dict[int, int] = {0: 1}
    running = 0
    total = 0
 
    for value in nums:
        running += value
        total += frequencies.get(running - k, 0)
        frequencies[running] = frequencies.get(running, 0) + 1
 
    return total

The initial 0: 1 represents the empty prefix before index 0. Without it, you'd miss every matching slice that begins at the first element. Looking up before recording also keeps that empty prefix separate from the current position.

Repeated prefix sums aren't noise — they're separate starting boundaries. If running - k has appeared three times, the current endpoint completes three different valid slices.

Time O(n) — one pass with O(1) expected map work per value. Space O(n) for the prefix-sum frequencies.