Array Hash Map Counting
Intermediate Level

Implement the subarraySumEqualsKCount method that counts subarrays whose sum equals k.

The input contains an integer array nums, its length size, and an integer k. Your task is to count how many continuous subarrays have a sum equal to k.

A subarray must use consecutive elements from the original array.

For example, in [1,1,1] with k = 2, the valid subarrays are the first two elements and the last two elements, so the answer is 2.

Example 1
Input:
nums (int[]) = [1,1,1]
size (int) = 3
k (int) = 2
Return:
(int) 2
Example 2
Input:
nums (int[]) = [1,2,3]
size (int) = 3
k (int) = 3
Return:
(int) 2
Example 3
Input:
nums (int[]) = [1]
size (int) = 1
k (int) = 0
Return:
(int) 0

Use prefix sums and a map of how many times each prefix sum has appeared.

At any index, suppose the current prefix sum is sum. A previous prefix sum equal to sum - k means the elements between that previous position and the current position form a subarray with sum k.

Add the frequency of sum - k to the answer, then store the current prefix sum in the map.

Pseudocode:

function subarraySumEqualsKCount(nums, size, k):
    create map prefixCount
    prefixCount[0] = 1
    sum = 0
    count = 0
    for each number in nums:
        sum = sum + number
        need = sum - k
        if need exists in prefixCount:
            count = count + prefixCount[need]
        prefixCount[sum] = prefixCount[sum] + 1
    return count
Run your code to see the result.