This is a classic trap that catches even intermediate developers. Let’s see why two pointers collapse and why prefix math is the ultimate solution.

1. Why Two Pointers Fails on Negative Numbers

A sliding window relies on a fundamental monotonic invariant:

• If the current sum is too small, expanding the right pointer will increase the sum.
• If the current sum is too large, contracting the left pointer will decrease the sum.

The moment you introduce negative numbers, this invariant is destroyed! Expanding the right pointer might add -10, making the sum smaller. Shrinking the left pointer might drop -5, making the sum larger. You can no longer make greedy left/right decisions!

2. The Prefix Sum Invariant

Let prefix[i] be the cumulative sum from index 0 to i.

The sum of any contiguous subarray from index j + 1 to i is given by: sum(j+1 ... i) = prefix[i] - prefix[j].

We want this subarray sum to equal k:

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

The Breakthrough: As you iterate through the array maintaining a running prefix sum curr_sum, you simply ask the hash map: ‘How many times have we already seen a prefix sum equal to curr_sum - k in the past?’

Every time you find that value in the hash map, you have found a valid subarray that sums exactly to k!

Clean Python 3.12 Implementation

from collections import defaultdict

def subarray_sum(nums: list[int], k: int) -> int:
    """Counts subarrays summing to k in O(N) time and O(N) space."""
    # Base case: A prefix sum of 0 has occurred once (an empty prefix)
    prefix_counts: dict[int, int] = defaultdict(int)
    prefix_counts[0] = 1

    curr_sum = 0
    total_subarrays = 0

    for x in nums:
        curr_sum += x
        target = curr_sum - k
        
        # Add all occurrences of the complementary prefix sum
        if target in prefix_counts:
            total_subarrays += prefix_counts[target]
            
        # Record current prefix sum
        prefix_counts[curr_sum] += 1

    return total_subarrays

Why prefix_counts[0] = 1 is Critical

If you forget prefix_counts[0] = 1, any subarray that starts at index 0 and sums to k (e.g. nums = [3, ...], k = 3) will produce curr_sum = 3, and look for curr_sum - k = 0 in the map. Without the base case, it would fail to count that valid subarray!

Complexity Breakdown

• Time Complexity: O(N). Single pass through the array with O(1) hash map lookups.
• Space Complexity: O(N) to store prefix sum frequencies.