Subarray Sum Equals K
Given an integer array (which may contain negatives) and an integer k, count the number of contiguous subarrays whose elements sum to exactly k.
- 1 ≤ n ≤ 2 · 10^4
- -1000 ≤ nums[i] ≤ 1000
- -10^7 ≤ k ≤ 10^7
- *Contiguous* subarray sums
- Negative numbers break the sliding-window approach
- sum(i..j) = prefix[j] − prefix[i−1], so count earlier prefixes equal to
prefix[j] − k
If many queries ask for an aggregate over [l, r] and the aggregate has an inverse (sum, XOR, product without zeros), precompute P[i] = agg(a[0..i)) once so every query becomes P[r+1] - P[l]. Combined with a hash map of seen prefix values it counts subarrays with a given sum in one pass; the inverse trick (difference array) makes range updates O(1).
Maintain a running prefix sum and a hash map counting how many times each prefix value has appeared, seeded with {0: 1}. At each index the number of subarrays ending here with sum k equals the count of earlier prefixes equal to current - k; add it to the answer, then record the current prefix. This works with negatives because it never relies on monotonic sums.
- Brute force over all O(n^2) subarrays with a running sum is the fallback. A sliding window would only be valid if all numbers were positive.