Subarray Sum Equals K

Use prefix sums and a frequency map. Let sum be the total through the current index. A subarray ending here has sum k exactly when an earlier prefix had value sum-k, because subtracting the two prefixes leaves the subarray sum. Initialize freq[0]=1 so a prefix itself equal to k is counted. For each value, update sum, add freq[sum-k] to the answer if present, then increment freq[sum]. Count before incrementing so the current prefix is not incorrectly paired with itself when k=0. This works with negative numbers and zeros, unlike the common variable-window approach whose sum is not monotonic. Time is O(n) expected with hashing and space is O(n) in the worst case. Use a wide integer for the answer because there can be quadratically many valid subarrays.