Sliding window

left
right

Too small
left0
right0
curr_sum0
target0

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.

Brute-Force1 check

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:

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.

while numbers remain too small too big match no numbers left Update the sum sum vstarget? Expand rightright += 1 Shrink leftleft += 1 Found it No match

      
0 / 0