Finding contiguous subarrays that sum to a specific target k is a classic problem in computer science, frequently encountered in coding interviews. A naive brute-force approach, which involves checking every single possible subarray, would result in an O(N^2) time complexity, making it inefficient for larger input arrays. This problem can be solved much more efficiently by leveraging the powerful combination of prefix sums and a hash map (or dictionary in Python).

This optimized approach processes the array in a single pass, drastically reducing the time complexity. It intelligently uses previously computed information to determine valid subarrays, avoiding redundant calculations. By keeping track of running sums and their frequencies, it quickly identifies segments that sum to the target k.

Intuition:

Imagine you're tracking your daily bank balance. If your current balance is X, and you want to know if there was a specific past day where the total change in balance *since that day* (up to today) was exactly k, it means your balance on that past day must have been X - k. We use a hash map to efficiently record how many times each balance (running total or prefix sum) has occurred. If we are at a currentSum and we find that currentSum - k exists in our map, it implies that there are subarrays ending at the current position whose sum is exactly k.

Specifically, if Sum[0...j] - Sum[0...i-1] = k, then Sum[0...i-1] = Sum[0...j] - k. So, for each currentSum (which is Sum[0...j]), we check if (currentSum - k) has been encountered before as a prefix sum. The count of how many times (currentSum - k) appeared tells us how many such subarrays exist ending at the current index j.

Step-by-step thinking:

Initialize result = 0. This variable will store the final count of subarrays whose sum equals k.
Initialize current_sum = 0. This variable will keep track of the running sum of elements from the beginning of the array up to the current element being processed.
Initialize a hash map (dictionary in Python) called prefix_sums with {0: 1}. This map stores the frequency of each prefix sum encountered. The crucial entry (0, 1) signifies that a prefix sum of 0 exists once *before* we start iterating through the array. This handles cases where a subarray starting from index 0 itself sums to k (i.e., current_sum - k = 0, so we look for 0 in the map).
Iterate through each num in the input nums array, one by one.
In each iteration, add the current num to current_sum to update the running sum.
Calculate diff = current_sum - k. This diff represents the specific prefix sum that *must have occurred earlier* for the subarray ending at the current position to have a sum of k.
Check if diff exists as a key in the prefix_sums map. If it does, it means we have found prefix_sums.get(diff, 0) number of subarrays that sum to k. Add this count to our result.
Finally, update the prefix_sums map: increment the frequency of the current_sum. If current_sum is not yet in the map, add it with a frequency of 1. This ensures its availability for future calculations.
After iterating through all numbers in the array, return the accumulated result, which is the total count of subarrays summing to k.

Time Complexity: O(N)
Space Complexity: O(N)

Learn Complexity

212. Subarray Sum Equals K

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Constraints:

Learn

Topics

Companies

Hint

Use Cases