滑动窗口

核心思想

用两个指针 l 和 r 维护一个「窗口」，在数组或字符串上从左到右滑动，避免暴力枚举所有子数组，将 $O(n^2)$ 降至 $O(n)$。

适用条件：题目涉及连续子数组，且窗口状态随扩张/收缩具有单调性——扩张只往一个方向变，收缩只往另一个方向变。

---

保持单调性

单调性 = 边界移动方向固定，窗口状态可预测。

有单调性

条件：sum ≥ target
r 右移 → sum 只增
l 右移 → sum 只减
方向确定，可用双指针

无单调性

条件：distinct == k
同一个 r，l 在中间某点合法，两侧都不合法 → 合法区间是「孤岛」，双指针找不到

维护一个区间

有时候只是维护一个区间，也可以使用滑动窗口。例如，每次循环l和r都加1，维护一个相等的区间。

简单来说就是要能明确的知道当前状态下应该移动左窗口还是右窗口，这样才能逼近你想要的那个区间。

---

代码模板

第一步：确定窗口的起始边界st和长度step 可以不维护结束边界，结束边界en = st + step。注意这样写是一个左开右闭的区间 $[st,en)$

第二步：建立第一个滑动窗口 一般会从st遍历到en，比如窗口内所有值的总和

第三步：移动并维护滑动窗口 通过维护滑动窗口求出自己的需求。

举例：Leetcode拆炸弹

在这个例子中每次只要维护固定长度的窗口算出窗口每次的和即可

impl Solution {
    pub fn decrypt(code: Vec<i32>, k: i32) -> Vec<i32> {
        // 第一步：确定窗口的起始边界`st`和长度`step`
        let n: usize = code.len();
        let mut st: i32 = if k < 0 { n as i32 + k } else { 1 % n as i32 };
        let step = if k < 0 { -k } else { k };
 
        // 第二步：建立第一个滑动窗口
        let mut s: i32 = 0;
        for i in 0..step {
            s += code[(st + i) as usize % n];
        }
 
        // 第三步：移动并维护滑动窗口
        let mut ans: Vec<i32> = vec![s];
        for _ in 1..n {
            let en = (st + step) % n as i32;
            s -= code[st as usize];
            s += code[en as usize];
            st = (st + 1) % n as i32;
            ans.push(s);
        }
 
        ans
    }
}