k.
Problem
You are given an integer arraynums and an integer k. Return the total number of contiguous subarrays whose sum is equal to k.
The array can contain positive, negative, and zero values.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
nums = [1,1,1]
k = 2Output
2Solution
This problem can be solved using Prefix Sum and a HashMap. As we traverse the array, we maintain a running prefix sum.Suppose the current prefix sum is
sum. If there was an earlier prefix sum equal to sum - k, then the elements between that earlier position and the current position have a sum of exactly k.
Therefore, for every current prefix sum, we look for
sum - k in a HashMap. The HashMap stores the frequency of each prefix sum.
We store frequencies rather than just whether a prefix sum exists because the same prefix sum can occur multiple times, and each occurrence can produce a different subarray with sum
k.
We initialize the map with prefix sum
0 having a frequency of 1. This handles subarrays that start from index 0.
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> prefixSum = new HashMap<>();
// Empty prefix.
prefixSum.put(0, 1);
int sum = 0;
int count = 0;
for (int num : nums) {
sum += num;
// Check for a previous prefix sum.
count += prefixSum.getOrDefault(sum - k, 0);
// Store the current prefix sum.
prefixSum.put(sum, prefixSum.getOrDefault(sum, 0) + 1);
}
return count;
}
}
Complexity
Each element is processed once, and HashMap operations takeO(1) average time, resulting in O(n) time complexity.
The HashMap can store up to
n different prefix sums, requiring O(n) space.