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 subarraySumBruteForce(int[] nums, int k) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
int sum = 0;
for (int j = i; j < nums.length; j++) {
sum += nums[j];
if (sum == k) count++;
}
}
return count;
}Time: O(n^2) · Space: O(1)