Pattern visualizer
Count Subarrays with Given Sum
The instinct is a sliding window, and with a negative number in the array that instinct is wrong: adding an element can make the sum smaller, so the window never knows when to shrink. Prefix sums fix that. Let prefix(i) be the sum of nums[0..i]; then the sum of nums[l..r] is prefix(r) - prefix(l-1), because the front part nums[0..l-1] sits inside both and cancels. So a subarray ending at r has sum k exactly when some earlier prefix equals prefix(r) - k. Walk once, keep a map from prefix value to how many times it has occurred, and every index contributes its matching count in constant time. Seeding that map with prefix 0 is what allows a match to start at index 0 — the step most implementations forget. Animated on: nums = [1,2,3,-3,1,1,1], k = 3 — count the subarrays whose sum is exactly k..
Prefix sums plus a map of what has been seen
The sum of nums[l..r] is prefix(r) - prefix(l-1), because the shared front part nums[0..l-1] is inside both prefixes and subtracts away. So a subarray ending at r sums to 3 exactly when some earlier prefix equals prefix(r) - 3. That turns "try every pair of endpoints" into one left-to-right walk. The empty prefix 0 is filed before the walk starts, otherwise a subarray beginning at index 0 could never be counted.
1FUNCTION countSubarraysWithSum(nums, k)2 count <- 03 prefix <- 04 seen <- EMPTY MAP5 seen[0] <- 16 FOR r <- 0 TO LENGTH(nums) - 17 prefix <- prefix + nums[r]8 need <- prefix - k9 IF need IN seen10 count <- count + seen[need]11 seen[prefix] <- seen[prefix] + 112 RETURN count
← / → step · space play · Home restart