Return the number of contiguous subarrays whose elements sum to k. The array may contain negative numbers.
Before you code
A sliding window fails with negatives. A subarray ending here sums to k exactly when an earlier prefix sum equals the current one minus k.
Hints
- Keep a running sum and a map from prefix sum to how many times it has occurred, starting with
{0: 1}. - At each element, add
seen[S - k]to the answer, then record S. - O(n) time and space.
Production & complexity notes
When solving Subarray sum equals K on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Prefix sums to reinforce the underlying pattern.
What it practices
Prefix sums with a hash map, from Prefix sums.