A usage-billing job is given a day’s ledger deltas — charges, and refunds as negatives — and asked how many contiguous hour-windows summed to exactly k, a target credit they want to flag. The first version nested every start and end: for each hour i, add through every later hour j. Forty-eight staging slots returned before the page painted. A production year of hours was still adding windows when the request timed out.

Count the contiguous subarrays whose sum is k. Prefix sums already turn a slice sum into subtraction. Nested i..j uses that identity and still pays O(n²) additions. A shrinking sliding window would be the next guess on strictly positive deltas; refunds break the monotone contract, so that procedure is the wrong intended answer here.

This is an interview writeup, not a prefix-sum or hashing lecture. The prefix post owns exclusive vs inclusive tables. The hash table post owns buckets and collisions. Two Sum stores value → index so the complement is a lookup. Here we store prefix → how many times it appeared — the same complement, in prefix space.

The problem

Given an int[] nums and an int k, return how many contiguous subarrays sum to k. Empty is not a subarray. Overlapping windows each count. Order among the windows does not matter; the count does.

nums = [3, 1, 2, -3, 4], k = 3  →  4
       [3]  [1, 2]  [3, 1, 2, -3]  [2, -3, 4]

nums = [4, -1, 2, 1],    k = 3  →  2
       [4, -1]  [2, 1]

nums = [8],              k = 8  →  1

Note: If every value were positive, a shrinking window could hunt a unique running sum. Refunds make the window sum non-monotonic: expanding or shrinking no longer has a legal “too big / too small” rule. This prompt allows negatives, so the map of prefixes is the intended pass.

Nested windows are the honest brute force

Fix a start i, expand j to the right, and add. Every contiguous slice is visited once. Correct. Quadratic.

int subarraySumNested(int[] nums, int k) {
    int answer = 0;
    for (int i = 0; i < nums.length; i++) {
        int sum = 0;
        for (int j = i; j < nums.length; j++) {
            sum += nums[j];
            if (sum == k) {
                answer++;
            }
        }
    }
    return answer;
}

At n = 40 this is a rounding error. At n in the tens of thousands you paid a nested scan for a question a prefix map answers in expected constant time per index: how many earlier prefixes equal P - k?

One pass: store prefix counts, look up P - k

Walk left to right with a running total P. The identity is the prefix post’s subtraction, used as a count: a slice ending here sums to k exactly when some earlier prefix equals P - k.

Seed the map with prefix 0 seen once, so a window that starts at index 0 has a partner. Then, at each index:

  • Add nums[i] into P.
  • Add map.getOrDefault(P - k, 0) to the answer.
  • Then record this P: map.put(P, count + 1).

You never restart a scan from index 0. You never assume the values are positive. Same prefix cannot pair with itself as a zero-length slice because you look up before you insert the current P.

nums = [3, 1, 2, -3, 4]   k = 3
seed  map {0: 1}   prefix = 0   answer = 0

i=0  val=3   P=3   need=0    map {0:1}                 hit 1, answer=1, put 3 → 1
i=1  val=1   P=4   need=1    map {0:1, 3:1}            miss, put 4 → 1
i=2  val=2   P=6   need=3    map {0:1, 3:1, 4:1}       hit 1, answer=2, put 6 → 1
i=3  val=-3  P=3   need=0    map {0:1, 3:1, 4:1, 6:1}  hit 1, answer=3, put 3 → 2
i=4  val=4   P=7   need=4    map {…, 4:1}              hit 1, answer=4, put 7 → 1

The four hits are [3], [1, 2], [3, 1, 2, -3], and [2, -3, 4]. The Java is that walk:

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> prefixCount = new HashMap<>();
    prefixCount.put(0, 1);
    int prefix = 0;
    int answer = 0;
    for (int n : nums) {
        prefix += n;
        answer += prefixCount.getOrDefault(prefix - k, 0);
        prefixCount.put(prefix, prefixCount.getOrDefault(prefix, 0) + 1);
    }
    return answer;
}

Time is expected O(n) — one pass, one expected-O(1) lookup and put per index. Space is O(n) for the map. Worst-case hash degeneration is the same story the hash-table post already told; do not re-lecture it at the whiteboard unless they ask.

Note: Seed prefix 0 with count 1. Without it, a window that starts at index 0 never finds a partner — [8] with k = 8 would answer 0. Look up before you insert. Same rule as Two Sum. If you put first, a lone prefix pairs with itself as a zero-length slice. That is not in the array. The trap is loudest when k = 0: putting first counts the empty prefix at the same index; looking up first refuses it and still counts real windows whose sum is 0.

What interviewers usually poke next

  • Return the windows, not the count. A map of prefix → count forgets where those prefixes sat. Store lists of indices per prefix, or keep the starts and emit [left, right] (or copies of the slices) as you go.
  • All values positive. Then a sliding window is legal: grow right, shrink left, never restart. Say why the map is the wrong bill once they remove negatives.
  • A 2D matrix. How many sub-rectangles sum to k is the same identity with an extra nested loop on rows, still hashing prefix counts on the compressed columns.
  • Path Sum III on a tree. Same map on a root-to-node path; decrement the current prefix when you backtrack so sibling paths do not steal counts.
  • Overflow. prefix += n is fine for int in Java (wrap is defined). If they switch the type to a wider sum, name that.

You are done with this problem when you can say, out loud, why the nested windows are correct, why a sliding window lies once negatives appear, why the map is seeded with prefix 0, and why the lookup happens before the put.