Subarray Sum Equals K

Subarray sum equals k counts contiguous subarrays summing to exactly k. The array may contain negative numbers, and that single fact rules out the sliding window. A window works only when extending it moves the sum predictably. With negatives, adding an element can decrease the sum, so shrinking and growing no longer have reliable effects — the technique simply does not apply. Prefix sums do apply, and the reframing is the whole solution: - A subarray from i+1 to j sums to k exactly when prefix[j] − prefix[i] = k, so for each position the question becomes how many earlier prefixes equal currentSum − k. That converts a search over subarrays into a hash-map lookup, giving one pass instead of nested loops. The map stores how many times each prefix sum has occurred, not merely whether it has. Several earlier positions can share a prefix sum, and each represents a distinct valid subarray, so counting is essential — a set undercounts badly. Seeding the map with {0: 1} is what allows subarrays starting at index 0 to be found. Without it, any subarray beginning at the first element is missed, which is the standard bug across this whole family of problems. The order inside the loop matters: look up before inserting the current prefix sum. Inserting first lets a zero-length subarray match when k is 0. The brute force over all subarrays is O(n²), which is what the hash map replaces. One pass gives O(n) time and O(n) space.

Contiguous-sum questions over an array that may contain negatives point to prefix sums with a hash map, not a sliding window. The presence of negative values is the deciding signal, because it removes the monotonicity a window relies on. Continuous Subarray Sum and Subarray Sums Divisible by K are the same idea modulo an extra step.