Subarray sum / longest substring with property P → prefix sum or sliding window.

Problems about a contiguous subarray or substring satisfying a property P almost always reduce to one of two techniques: sliding window or prefix sum (+ hash map). The discriminating cue is whether the property is monotone as the window grows.

The decision table

When sliding window works

A window works when the property is monotone: extending the window can only push it toward (or away from) validity in one direction, so shrinking from the left restores validity. Examples: longest substring without repeating characters, minimum window substring, longest subarray with at most K distinct elements. All non-negative "sum ≤ target" problems qualify — adding elements only increases the sum.

// Template: longest window satisfying P
int left = 0;
for (int right = 0; right < n; right++) {
    add(arr[right]);
    while (!valid()) { remove(arr[left]); left++; }   // shrink until valid
    best = Math.max(best, right - left + 1);
}

When you must use prefix sum + hash map

The moment negative numbers appear in a "subarray sums to exactly K" problem, the window breaks — adding an element can decrease the sum, so there's no monotone shrink condition. Instead, use prefix sums: sum(i..j) = prefix[j] - prefix[i-1]. Store running prefix sums in a hash map; for each prefix[j], the count of earlier prefixes equal to prefix[j] - K is the number of subarrays ending at j with sum K.

// Subarray Sum Equals K (works with negatives)
Map<Long, Integer> seen = new HashMap<>();
seen.put(0L, 1);                       // empty prefix
long prefix = 0; int count = 0;
for (int x : nums) {
    prefix += x;
    count += seen.getOrDefault(prefix - K, 0);   // earlier prefix that makes sum K
    seen.merge(prefix, 1, Integer::sum);
}

The recognition rule

• "Longest/shortest contiguous window where P holds" + property is monotone → sliding window.
• "Count/find subarrays summing to exactly K" + negatives possible → prefix sum + hash map.
• "Many range-sum queries on a static array" → prefix sum array for O(1) queries.