Given a list of positive numbers and a target, find a continuous subarray that adds up to the target.
Examples
Your turn
Drag across the numbers to pick a subarray.
The sliding window is a much faster method for finding if a subarray exists compared to the brute-force solution:
This is because the brute force solution blindly considers all possible subarrays.
A sliding window tracks the sum in the current subarray. The sum is then used either shrink the subarray from the left or to expand it from the right.
See if you can work out which choice to make to the subarray on the right when the current sum exceeds the target:
Now the sum is under the target. See if you can work out which choice to make:
By choosing to shrink the subarray here, we skip a number of unnecessary checks.
By choosing to extend the subarray here, we skip a number of unnecessary future checks.
Here’s what the sliding window algorithm looks like in action. Notice how comparing the sum and the target always tells us whether to expand or shrink the window.
What’s the next step in the algorithm after comparing the sum to the target?
Are there any numbers left to add?
Each move changes one variable, and the sum follows.
Every line of code is one step of the flowchart.