Hints — p31 Subarray Sum Equals K

Read one at a time.

Hint 1 — Brute first. Two nested loops, accumulate sum from i to j, increment counter on match. O(N²). State this, then optimize.

Hint 2 — The prefix-sum identity. Let prefix[t] = nums[0] + ... + nums[t-1] (with prefix[0] = 0). Then sum(i, j) = prefix[j+1] - prefix[i]. So sum(i, j) == k iff prefix[j+1] == prefix[i] + k, i.e., for each right endpoint j, count how many earlier prefix values equal prefix[j+1] - k.

Hint 3 — Hashmap of prefix counts. Single pass. Maintain a running sum and a count[value] → frequency map. For each new prefix value p, look up count[p - k] (that’s how many subarrays ending here sum to k), then increment count[p]. O(N).

Hint 4 — Seed count[0] = 1. Before iteration, the prefix-sum is 0 (empty prefix). Without seeding, a subarray that itself sums to k (starting from index 0) is missed. Memorize: count[0] = 1 always.

Hint 5 — Don’t reach for sliding window. Sliding window only works when nums is all-non-negative (the running sum is monotonic in window growth). With negatives, the monotone property fails. Prefix sum + hashmap is the correct tool.

If still stuck: see solution.py. 8 lines for the optimal. Read the INVARIANT comment above count.