Count Subarrays with Given Sum using Prefix Sum and HashMap Optimal Solution

Given an integer array arr and a target sum k, your task is to find the total number of continuous subarrays whose elements add up to exactly k.

A subarray is a sequence of elements that appears in the same order in the array and is contiguous. The same element can be included in multiple subarrays if it appears in different positions.

This problem is common in applications involving range-based queries, financial analysis, and interval sum counting.

To count how many subarrays sum to a given number k, we can use a clever technique based on prefix sums and a hash map to store frequency of those sums. This approach avoids nested loops and gives us a highly efficient solution with linear time complexity.

Understanding the Core Idea

Imagine you're scanning the array from left to right and keeping track of the sum of all elements you've seen so far. This is called the prefix sum. At any position i, the sum of the subarray from some previous position j to i is simply prefix[i] - prefix[j-1].

Now, if you know that prefix[i] - k has been seen before, that means there exists a subarray that ends at position i and adds up to k.

Different Cases to Consider

• Exact match: If the current prefix sum is equal to k, it means the subarray starting from index 0 to current index forms a valid subarray.
• Matching a previous prefix: If you've previously seen a prefix sum of curr_sum - k, it means all subarrays that end at the current index and start after those earlier indices add up to k. You can count how many times that prefix occurred and add that to your answer.
• Negative numbers and zeroes: The method works even if the array has negative numbers or zeros. For example, in an array like [1, -1, 0] with k = 0, multiple combinations are valid.
• Empty array: There are no subarrays to count, so the result is 0.
• All zeros: In arrays like [0, 0, 0], every subarray (length 1 to full length) adds up to 0. This results in multiple overlapping subarrays that all qualify.

Why This Works

By storing how often each prefix sum has appeared, we avoid re-checking every possible subarray. We can just look up how many times we've seen prefix_sum - k in constant time using a hash map. This optimization turns a brute-force O(n²) approach into a fast O(n) solution.

This method is highly effective, scalable, and works for large arrays with positive, negative, or zero values.

1. Given an array arr and a target k.
2. Initialize a prefix sum curr_sum = 0 and a hash map prefix_count to store frequency of prefix sums.
3. Initialize count = 0.
4. Iterate through the array:
5. → Add current element to curr_sum.
6. → If curr_sum == k, increment count by 1.
7. → If curr_sum - k exists in prefix_count, add its frequency to count.
8. → Update the frequency of curr_sum in prefix_count.
9. Return the total count.