Number of Subarrays with Sum K

Count (not just find the longest) subarrays summing to k. [1,2,3,-3,1,1,1,4,2,-3], k=3 → 8. (LeetCode 560)

Brute force: three nested loops generating every subarray and summing it — O(n³), reducible to O(n²) with a running sum.

Optimal — prefix sum + hashmap of counts: for each prefix sum, check how many earlier prefix sums equal prefixSum - k — each one marks a valid subarray ending here. Track counts (not just first-seen index) since multiple earlier positions can share the same prefix sum.

count = 0;
prefixSum = 0;
map = new HashMap<Integer, Integer>();
map.put(0, 1); // empty prefix, for subarrays that sum to k starting at index 0

for (int num : arr) {
    prefixSum += num;

    if (map.containsKey(prefixSum - k)) {
        count += map.get(prefixSum - k);
    }

    map.put(prefixSum, map.getOrDefault(prefixSum, 0) + 1);
}

Time: O(n). Space: O(n).