Start from the invariant.
66 of 66 templates
Sliding window
Sliding window
Maintain a valid contiguous interval.
Interview essentialsWhen to use it
Find the longest contiguous array segment whose sum is at most a limit. Every value must be nonnegative.
What stays true
After shrinking, sum equals the total in [left, right] and is at most the limit. Removing another left value cannot produce a longer valid segment ending here.
- Time
- O(n)
- Extra space
- O(1)
sliding_window.rs
/// Longest segment with sum <= limit; every value must be nonnegative.
fn longest_window(nums: &[i64], limit: i64) -> usize {
if limit < 0 {
return 0;
}
let (mut left, mut total, mut best) = (0, 0i64, 0);
for right in 0..nums.len() {
total += nums[right];
while total > limit {
total -= nums[left];
left += 1;
}
best = best.max(right + 1 - left);
}
best
}
Functions and structs only. Add fn main with your judge’s input handling.
nums = [2, 1, 3, 1], limit = 4 → 2. Both [2, 1] and [3, 1] have length 2.
Keep the sum at most 4
Extend
- 02(active)
- 11(active)
- 23
- 31
[2, 1] sums to 3 and has length 2.
1 / 4