Subarray Sum Equals K Explained: Counting [1, -1, 1]

Imagine you are handed the array $\text{nums}=[1,-1,1]$ and asked to find how many contiguous subarrays sum up to $k=1$. A contiguous subarray is any unbroken slice of the array, such as index 0 to 0, or index 0 to 2. Without any clever techniques, your first instinct might be to write two nested loops to check every possible starting point and ending point. For an array of size $n$, this brute-force approach requires evaluating roughly $O(n^2)$ slices, and if you recalculate sums from scratch each time, you might even hit $O(n^3)$ time complexity. As arrays grow from three elements to thirty thousand elements, checking every single window becomes computationally impossible. We need a way to look at running totals so we don't have to keep re-adding past elements.

Instead of recalculating the sum of every contiguous slice from scratch, we define a running total called the prefix sum, denoted $P_i$, which accumulates all elements from index 0 up to index $i$. For our locked working example of $\text{nums}=[1,-1,1]$, the prefix sums as we walk through the array are 1, then 0, and finally 1. Notice how the sum of any subarray from index $i$ to $j$ is simply the difference between two prefix sums: $P_j-P_{i-1}$. We are no longer looking at nested index loops; we are looking at running totals and asking how often a required past prefix sum has appeared. This transforms a range-sum problem into a point-lookup frequency problem.

Now that we have the prefix sum mental model, let's execute the algorithm on our locked example: $\text{nums}=[1,-1,1]$ and $k=1$. Instead of checking every starting index, we maintain a running prefix sum $P$ and a hash map frequency table $\text{map}$ that tracks how many times each prefix sum has appeared so far. We initialize the map with $\{0:1\}$ to handle any subarray that starts directly from index 0.

You have seen how the prefix sum frequency map tracks past values to instantly find valid subarrays for $\text{nums}=[1,-1,1]$ and $k=1$. Now, test your understanding on a slightly altered array to see if you can trace the state transitions yourself. Consider $\text{nums}=[2,0,2]$ and $k=2$. Imagine stepping through each index while updating your running prefix sum and checking the frequency map for $P-k$. Think about how the zero in the middle alters the running prefix sum without changing the target count.

We began with the combinatorial challenge of counting subarrays in our working example nums = [1, -1, 1] with $k=1$, moving from $O(N^2)$ checks to an $O(N)$ single-pass frequency map. The true power of this mental model lies in its invariance to domain shifts. When a problem asks for continuous segments matching a target sum, the prefix sum equation $P_j-P_i=k$ remains our bedrock regardless of whether the array contains negative numbers, zeros, or streams of identical digits. By maintaining the running prefix sum and checking our frequency hash map, we transform range-query problems into point-lookup problems.