Maintain the sum of the window06.01
Window sum updates in O(1) per move: add a[R] when R advances, subtract a[L] when L advances. After every move, sum equals a[L]+…+a[R].
Do not rescan a[L..R]. Drop uses the old a[L] before L++. Start from a real [L,R].
worked examples
Same skill, three traces. Read all three before you try it.
01expand - given
a = [4, 1, 9, 1],L=0- walk
R=0+4→4R=1+1→5R=2+9→14- result
- sum
14on[0,2]
02shrink - given
a = [4, 1, 9, 1],L=0R=2, sum14- walk
drop
a[0]=4L0→114-4=10- result
- sum
10on[1,2]
03slide length 3 - given
a = [4, 1, 9, 1], first[0,2]- walk
14drop
4adda[3]=1→11- result
- sum
11on[1,3]
Write
Expand to
On
windowSum(a).a is an array of integers. L is the left index. R is the right index. The window includes a[L..R]. sum is a[L]+…+a[R].Expand to
R=2, shrink once, then slide length 3. Print sum after each move. Return nothing.On
[4, 1, 9, 1] sums are 14, then 10, then 11.constraintsa is nonempty. All values are integers. Start with a real window [L, R].
- Maximum Average Subarray I0/3 skills ready · sliding window · easyopen
- Minimum Size Subarray Sum0/3 skills ready · sliding window · mediumopen
- Maximum Average Subarray I0/3 skills ready · sliding window · easyopen
- Minimum Size Subarray Sum0/3 skills ready · sliding window · mediumopen
Every Check with Awel is frozen here. Open one to read the code or load it back into the editor.