Prefix Sum

Opening scenario

Subarray Sum Equals K (LC 560). Given an integer array nums (values may be negative) and an integer k, return the number of nonempty contiguous subarrays whose sum equals k. Then the harder follow-up: Count of Range Sum (LC 327) — count subarrays whose sum lies in [lower, upper].

LC numbers identify LeetCode problems.

Try [1, -1, 1] with k = 1: three different subarrays qualify. How can you count their boundaries without repeatedly summing the same elements?

Question progression

Q1 — Why can't you slide a window here?

Question: "Contiguous subarray with sum k" smells like sliding window. Why does the window approach break on LC 560?

Reasoning: Sliding window needs a monotone validity rule — growing the window must move the sum in a predictable direction. With negative numbers, adding an element can decrease the sum, then a later element can increase it again. So a window that overshoots k…