Count the subarrays whose elements sum to k, where the values may be negative.

Short answer

Count subarrays summing to k by keeping a running prefix sum and a hash map from prefix-sum value to frequency. At each element, add the count for sum - k before recording the current sum, seed the map with {0: 1}, and use this instead of sliding window when numbers may be negative.

Reading the constraint first

The presence of negative values is not colour in the problem statement, it is the whole reason a hash map is required. A sliding window works when growing the window monotonically increases the sum and shrinking it decreases it, because that monotonicity is what justifies moving the left boundary forward and never back. Negatives destroy it: extending the window can lower the sum, so a window you rejected might have become valid two elements later, and the window's central assumption is gone.

What survives is the prefix sum. If P(i) is the sum of the first i elements, the sum of the subarray (j, i] is P(i) - P(j). You want that to equal k, so for each i you want the number of earlier j with P(j) = P(i) - k. Counting those in constant time is exactly what a hash map buys you, and it is the whole algorithm.

The solution, and the two lines that decide it

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> counts = new HashMap<>();
    counts.put(0, 1);                              // the empty prefix, before any element
    int sum = 0, total = 0;

    for (int x : nums) {
        sum += x;
        total += counts.getOrDefault(sum - k, 0);   // look up BEFORE recording this prefix
        counts.merge(sum, 1, Integer::sum);
    }
    return total;
}

Seeding the map with {0: 1} is not a defensive nicety. Without it, a subarray that starts at index 0 has no earlier prefix to subtract from, so every answer anchored at the beginning of the array is silently lost, and the function returns a plausible-looking wrong number that passes small hand-written tests.

The ordering of the two statements inside the loop matters for k = 0. If you record sum first and then look up sum - k, you find the entry you just inserted and count the empty subarray ending at the current index, inflating the total by n. Doing the lookup first means the map contains only strictly earlier prefixes, which is what the derivation says it should contain.

Time is O(n) with one hash operation per element. Space is O(n) in the worst case, when every prefix sum is distinct. That worst case is the trade: you are paying a linear amount of memory to avoid the quadratic scan, and the memory is proportional to input size rather than to the answer.

What the map demands of its keys

Here the keys are boxed Integer values, whose hashCode and equals are already correct, so the caveats stay invisible. They stop being invisible the moment a key is a domain object - a coordinate pair, a normalised string, a composite id.

Three things have to hold. Equal objects must return equal hash codes, or two keys that are equals land in different buckets and the map appears to contain a duplicate. Unequal objects may share a hash code, which is legal and merely costs a chain walk, so equals still has to be exact. And the hash code must not change while the object is a key: mutating a field that participates in hashCode after insertion leaves the entry sitting in a bucket that lookups will never search again, so the value is unreachable but still retained. In Java the cheap correct route is a record, which derives both methods from the components; if you write them by hand, both methods must be derived from the same fields.

When a hash map is the wrong instrument

The default assumption that a hash map is free is worth resisting, and an interviewer who asks the fourth follow-up above is checking whether you can.

• The keys are dense small integers. An int[] indexed directly beats a HashMap<Integer, Integer> on both memory and cache behaviour, with no boxing and no hashing.
• You need order. A hash map has none, and reaching for it and then sorting the entries afterwards often means a sorted structure or a counting sort was the right answer from the start.
• Tail latency matters more than mean. Individual operations are O(1) expected, not worst case, and a resize touches every entry. In a request path with a p99 budget, an amortised bound quoted as if it were a guarantee is a real mistake.
• The keys are attacker-controlled. Colliding keys can be manufactured. Java's HashMap converts a long chain to a red-black tree, capping a degenerate bucket at O(log n) rather than O(n), but the mitigation is worth knowing rather than assuming.
• n is tiny. For a handful of elements a linear scan over an array wins outright, because hashing and allocation dominate.

The strong version of this answer states the trade in one sentence - linear extra memory buys the removal of a nested loop - and then says where that trade stops being worth making. Candidates who can only argue the first half sound like they learned the technique from an editorial rather than from using it.

---

© 2026 Preptima. Originally published at preptima.com.