Sliding window fails the moment an array can contain negative numbers: growing the window no longer grows the sum, so “shrink while too big” stops making sense. It also fails when a problem asks you to count subarrays rather than find the best one.

The pattern that handles both is prefix sums plus a hash map. It rests on one identity:

$\text{sum}(i..j) = \text{prefix}[j] - \text{prefix}[i-1]$

Rearranged, a subarray ending at jj sums to kk exactly when some earlier prefix equals $\text{prefix}[j] - k$. So instead of searching for subarrays, you count prefix values you have already seen — one pass, one dict, $O(n)$.

What you’ll learn

• The prefix-sum identity, and the rearrangement that turns it into a lookup.
• Why the map must be seeded with {0: 1}{0: 1}, and what breaks without it.
• Counting occurrences vs. remembering the earliest index — the two flavours, and which each problem needs.
• The remainder and balance transforms that make this pattern cover far more than plain sums.
• Three real LeetCode problems solved in the browser: 560, 974, 525.

The cue

The template

Two flavours. Which one you need depends on whether the answer is a count or a length.

# FLAVOUR 1 -- COUNT subarrays. Map: prefix value -> how many times seen.
def count_subarrays_with_sum(nums, k):
    seen = {0: 1}          # one empty prefix, so subarrays starting at index 0 count
    running = 0
    count = 0
    for x in nums:
        running += x
        count += seen.get(running - k, 0)      # every earlier match is a subarray
        seen[running] = seen.get(running, 0) + 1
    return count
 
 
# FLAVOUR 2 -- LONGEST subarray. Map: prefix value -> EARLIEST index seen.
def longest_subarray_with_sum(nums, k):
    first = {0: -1}        # empty prefix sits "before" index 0
    running = 0
    best = 0
    for i, x in enumerate(nums):
        running += x
        if running - k in first:
            best = max(best, i - first[running - k])
        if running not in first:               # only record the FIRST occurrence
            first[running] = i
    return best
 
 
print(count_subarrays_with_sum([1, 1, 1], 2))          # 2
print(longest_subarray_with_sum([1, -1, 5, -2, 3], 3))  # 4

# FLAVOUR 1 -- COUNT subarrays. Map: prefix value -> how many times seen.
def count_subarrays_with_sum(nums, k):
    seen = {0: 1}          # one empty prefix, so subarrays starting at index 0 count
    running = 0
    count = 0
    for x in nums:
        running += x
        count += seen.get(running - k, 0)      # every earlier match is a subarray
        seen[running] = seen.get(running, 0) + 1
    return count
 
 
# FLAVOUR 2 -- LONGEST subarray. Map: prefix value -> EARLIEST index seen.
def longest_subarray_with_sum(nums, k):
    first = {0: -1}        # empty prefix sits "before" index 0
    running = 0
    best = 0
    for i, x in enumerate(nums):
        running += x
        if running - k in first:
            best = max(best, i - first[running - k])
        if running not in first:               # only record the FIRST occurrence
            first[running] = i
    return best
 
 
print(count_subarrays_with_sum([1, 1, 1], 2))          # 2
print(longest_subarray_with_sum([1, -1, 5, -2, 3], 3))  # 4

How it works

Take nums = [3, 4, 7, 2, -3, 1, 4, 2]nums = [3, 4, 7, 2, -3, 1, 4, 2], k = 7k = 7:

Four subarrays: [3,4][3,4], [7][7], [7,2,-3,1][7,2,-3,1], [1,4,2][1,4,2]. Notice the seed firing at i = 1i = 1 — that is the subarray starting at index 00, and it is exactly what a missing {0: 1}{0: 1} would lose.

The variant map

The power of this pattern is that you can transform the array first, turning an unrelated-looking condition into “sum equals a target”.

Practice — real LeetCode problems

LC 560 — Subarray Sum Equals K · Medium

Problem. Given an integer array numsnums and an integer kk, return the total number of contiguous subarrays whose sum equals kk.

Constraints. 1 <= len(nums) <= 2 * 10^41 <= len(nums) <= 2 * 10^4, -1000 <= nums[i] <= 1000-1000 <= nums[i] <= 1000, -10^7 <= k <= 10^7-10^7 <= k <= 10^7. Note the negatives — this is why it is not a sliding window.

Examples. nums = [1,1,1], k = 2nums = [1,1,1], k = 2 gives 22 · nums = [1,2,3], k = 3nums = [1,2,3], k = 3 gives 22 · nums = [1,-1,0], k = 0nums = [1,-1,0], k = 0 gives 33

LC 974 — Subarray Sums Divisible by K · Medium

Problem. Return the number of contiguous subarrays whose sum is divisible by kk.

Constraints. 1 <= len(nums) <= 3 * 10^41 <= len(nums) <= 3 * 10^4, -10^4 <= nums[i] <= 10^4-10^4 <= nums[i] <= 10^4, 2 <= k <= 10^42 <= k <= 10^4.

Examples. nums = [4,5,0,-2,-3,1], k = 5nums = [4,5,0,-2,-3,1], k = 5 gives 77 · nums = [5], k = 9nums = [5], k = 9 gives 00 · nums = [-1,2,9], k = 2nums = [-1,2,9], k = 2 gives 22

LC 525 — Contiguous Array · Medium

Problem. Given a binary array numsnums, return the length of the longest contiguous subarray with an equal number of 00s and 11s.

Constraints. 1 <= len(nums) <= 10^51 <= len(nums) <= 10^5, nums[i]nums[i] is 00 or 11.

Examples. nums = [0,1]nums = [0,1] gives 22 · nums = [0,1,0]nums = [0,1,0] gives 22 · nums = [0,1,1,1,1,1,0,0,0]nums = [0,1,1,1,1,1,0,0,0] gives 66 · nums = [1,1,1]nums = [1,1,1] gives 00

LeetCode problem set

Interview follow-ups

Edge-case checklist

• k = 0k = 0 — forces the count-before-record ordering; [1,-1,0][1,-1,0] is the test.
• Negative numbers — the entire reason for this pattern; make sure nothing in your solution assumes monotonicity.
• Zeros in the array — create repeated prefix values and therefore extra valid subarrays; they must be tallied, not deduplicated.
• Whole array is the answer — verifies the seed entry works.
• No valid subarray — must return 00, not -1-1 or float("inf")float("inf").
• Single element — [5], k = 5[5], k = 5 gives 11; [5], k = 9[5], k = 9 gives 00.
• Overflow — irrelevant in Python (arbitrary-precision ints), but worth naming if the interviewer thinks in C++ or Java.
• Earliest-index guard (length variants) — never overwrite a balance already in the map.

Recap

• $\text{sum}(i..j) = \text{prefix}[j] - \text{prefix}[i-1]$, rearranged into a lookup: a subarray ending here hits the target when running - krunning - k has been seen before.
• Two flavours: count occurrences ({0: 1}{0: 1}) for “how many”, earliest index ({0: -1}{0: -1}) for “how long”.
• Seed the map, and for length variants never overwrite an existing key.
• Count before recording so k = 0k = 0 cannot match a zero-length subarray.
• Transform first, then apply the template: % k% k for divisibility, +1/-1+1/-1 for equal counts, odd/evenodd/even for parity counts. That is what makes one small template cover a dozen problems.
• Choose this over a window whenever values can be negative, or the question asks for a count.

Next: Kadane and Maximum Subarray — the other classic answer to “contiguous subarray with negatives”, when you want the best sum rather than a count.