Given an array of integers nums and an integer k, return the total number of contiguous subarrays whose sum equals k.
Example 1
Input: nums = [1,1,1], k = 2
Output: 2
Explanation: Two subarrays sum to 2: [1,1] (indices 0-1) and [1,1] (indices 1-2).
Example 2
Input: nums = [1,2,3], k = 3
Output: 2
Explanation: [1,2] and [3] both sum to 3.
1 <= nums.length <= 2 * 10^4-1000 <= nums[i] <= 1000-10^7 <= k <= 10^7The brute force checks every subarray's sum directly — O(n^2). What running value, tracked as you scan once, could avoid recomputing each subarray's sum from scratch?
If prefixSum[j] - prefixSum[i] == k, the subarray between i+1 and j sums to k. Rearranged: prefixSum[i] == prefixSum[j] - k.
A hash map from 'prefix sum value seen so far' to 'how many times' turns the search for prefixSum[i] into an O(1) lookup instead of an O(n) scan.
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> prefixCount = new HashMap<>();
prefixCount.put(0, 1); // empty prefix — needed so a subarray starting at index 0 can be counted
int sum = 0, count = 0;
for (int n : nums) {
sum += n;
count += prefixCount.getOrDefault(sum - k, 0);
prefixCount.merge(sum, 1, Integer::sum);
}
return count;
}Time: O(n) · Space: O(n)