Subarray Sum Equals K

The sum of a subarray is a difference of two prefix sums. Let P[t] stand for the sum of the first t elements; then the sum of nums[i..j] is P[j+1] - P[i]. Setting that equal to k and rearranging, a subarray ending at the current position has sum k exactly when some earlier prefix equals current prefix - k. The problem is therefore not “sum every window” but “count earlier prefixes equal to current prefix - k” — and a hash map of prefix frequencies answers that in constant time.

Brute Force: Every Starting Point

Time O(n²)Space O(1)

Fix a starting index and walk right, adding each element as you go. After every extension you have one more candidate subarray, so comparing the running total with k counts them all. The inner loop must not stop early: values can be negative, so a total that misses k may still reach it later, and a total that equals k may be followed by a zero-sum stretch that equals k again.

class Solution:
    def subarraySum(self, nums: list[int], k: int) -> int:
        count = 0
        n = len(nums)
        for start in range(n):
            total = 0
            for end in range(start, n):
                total += nums[end]
                if total == k:
                    count += 1
        return count

Why it is quadratic: there are O(n²) subarrays and each one is examined once, so the running total makes the whole enumeration O(n²) time. The only extra memory is a handful of counters, so space is O(1). With n up to 2 * 10^4 this is roughly 2 * 10^8 additions — too slow, which is what the prefix-sum map removes.

Prefix Sum + Frequency Map

OptimalTime O(n)Space O(n)

Keep a running prefix s and a map seen from prefix value to how many times it has occurred. Before inserting the current prefix, ask how many earlier prefixes equal s - k; each one is the start of a subarray ending here, so add that count to the answer. Then record the current prefix.

The initial entry seen = {0: 1} is the empty prefix before the array — it is what lets a subarray that starts at index 0 be counted. Lookup before insert is the other half of the trick: it guarantees the current index never pairs with itself, so every subarray is counted once, at its right endpoint.

class Solution:
    def subarraySum(self, nums: list[int], k: int) -> int:
        count = 0
        prefix = 0
        seen = {0: 1}          # empty prefix, for subarrays starting at index 0
        for x in nums:
            prefix += x
            count += seen.get(prefix - k, 0)   # count earlier partners
            seen[prefix] = seen.get(prefix, 0) + 1
        return count

Why it is linear: each element is touched once, and each iteration does one map lookup and one map write, both O(1) expected time. The map can hold one distinct prefix per index in the worst case, so space is O(n). Note that a sliding window does not work here — negative numbers break the monotonicity that shrinking depends on, while the prefix map handles them naturally.

Watch how each new prefix turns into a lookup and how many earlier prefixes answer it. On the first example, nums = [1, 1, 1] with k = 2:

start

prefix s0needs s-k—matches0ans so far0

Input (target k = 2)

Prefix map (value × count)

0×1

every prefix equal to s - k ends one subarray at the current index — count them, then store the current prefix

1 / 8

currentcomparingseen

A running prefix sum turns every subarray sum into a difference of two prefixes. Seed the map with prefix 0 seen once, standing for the empty prefix before the array.

The second trace, nums = [1, -1, 1] with k = 1, shows a repeated prefix: once 0 has been stored twice, a single lookup finds two partners at once, and the answer jumps by two.