Understanding the Problem

We need to count every contiguous subarray that sums to exactly k. Not find one, not find the longest, but count all of them.

A subarray is defined by its start and end indices. For an array of length n, there are n * (n + 1) / 2 possible subarrays. The brute force approach checks every single one, but can we do better?

The key observation is this: if we know the cumulative sum from index 0 to index j (call it prefixSum[j]), and we know the cumulative sum from index 0 to some earlier index i (call it prefixSum[i]), then the sum of the subarray from i+1 to j is simply prefixSum[j] - prefixSum[i]. If that difference equals k, we've found a valid subarray. So the question becomes: for each position j, how many earlier prefix sums equal prefixSum[j] - k?

Key Constraints:

nums.length up to 2 * 10^4 means O(n^2) is borderline (about 4 \* 10^8 operations in the worst case), so an O(n) solution is preferred
Elements can be negative (-1000 <= nums[i] <= 1000), which rules out sliding window approaches that rely on the sum growing as the window expands
k can be negative too, so we can't make assumptions about the target sum's sign

Approach 1: Brute Force

Intuition

The most direct approach: try every possible subarray, compute its sum, and check if it equals k. We fix a starting index i, then extend the subarray one element at a time to each ending index j. By keeping a running sum as we extend, we avoid recomputing the sum from scratch each time.

Algorithm

Initialize a counter count to 0
For each starting index i from 0 to n-1:

Initialize sum to 0
For each ending index j from i to n-1:

Add nums[j] to sum
If sum equals k, increment count

Return count

Example Walkthrough

1i=0, j=0: sum=1, k=3. sum!=k. count=0

1/7

Code

Complexity Analysis

Time Complexity: O(n^2). We have two nested loops. The outer loop runs n times, and for each iteration, the inner loop runs up to n times. Each inner iteration does O(1) work.
Space Complexity: O(1). We only use a few integer variables regardless of input size.

For every starting index, we scan forward through the rest of the array. What if we computed the prefix sum once and used a hash map to instantly look up how many earlier prefix sums would form a valid subarray ending at the current position?

Approach 2: Prefix Sum + Hash Map

Intuition

The sum of a subarray from index i+1 to index j can be written as prefixSum[j] - prefixSum[i]. If we want this to equal k, we need prefixSum[i] = prefixSum[j] - k. So as we walk through the array building up our prefix sum, at each position j we ask: "How many times have I seen a prefix sum equal to currentPrefixSum - k?"

We track these frequencies in a hash map. One crucial detail: we initialize the map with {0: 1}. This accounts for subarrays that start from the very beginning of the array (where the prefix sum itself equals k).

Why does this work?

The prefix sum transforms the problem from "find subarrays with sum k" to "find pairs of prefix sums that differ by k." This is essentially a variant of the Two Sum problem. In Two Sum, you look for pairs that add up to a target. Here, you look for pairs that differ by a target. The hash map lets you do each lookup in O(1), turning the entire algorithm into a single pass.

The {0: 1} initialization is the subtlest part. Without it, you'd miss any subarray that starts at index 0 and sums to k. For example, with nums = [3], k = 3, the prefix sum after the first element is 3. We need prefixSum - k = 0 to be in the map, and the only way that happens is if we seed it there.

Algorithm

Initialize count = 0, prefixSum = 0, and a hash map prefixCount with {0: 1}
For each element num in the array:

Add num to prefixSum
If prefixSum - k exists in prefixCount, add its frequency to count
Increment prefixCount[prefixSum] by 1

Return count

Example Walkthrough

1Init: prefixSum=0, count=0, map={0:1}

1/6

Code

Complexity Analysis

Time Complexity: O(n). We make a single pass through the array. At each element, we do one hash map lookup and one hash map insert, both O(1) on average.
Space Complexity: O(n). In the worst case, every prefix sum is unique, so the hash map stores n + 1 entries (including the initial {0: 1}).

Subarray Sum Equals K

Understanding the Problem

Key Constraints:

Approach 1: Brute Force

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Prefix Sum + Hash Map

Intuition

Algorithm

Example Walkthrough

Code

Get Premium