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) =
3k (int) =
2Returns (int)
2Example 2
Input
nums (int[]) =
[1,2,3]size (int) =
3k (int) =
3Returns (int)
2Example 3
Input
nums (int[]) =
[1]size (int) =
1k (int) =
0Returns (int)
0Use 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 countReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run