Subarray Sum
Learn Subarray Sum (Hashing, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Subarray Sum Problems - Which Tool Fits? "Subarray sum" problems come in several flavors, and picking the right tool matters: All positive numbers, exact target: Sliding Window - grow/shrink based on whether the sum is too small or too large. Numbers can be negative, exact target: Prefix Sum + HashMap - sliding window breaks because shrinking doesn't monotonically decrease the sum anymore. Just need the maximum sum, no target: Kadane's Algorithm.