JZTXT

滑动窗口总结

发布时间 2023-03-31 10:59:01作者: Co3y

前言

滑动窗口是双指针的一种特例，可以称为左右指针，在任意时刻，只有一个指针运动，而另一个保持静止。滑动窗口路一般用于解决特定的序列中符合条件的连续的子序列的问题。

一、算法应用场景

关键词：

1.满足XXX条件（计算结果、出现次数、同时包含）
2.最长/最短/或最值
3.子串/子数组/子序列
最最最重要的提示点是：必须是连续的，否则不可以用滑动窗口

二、滑动窗口代码模板

寻找最长模板

初始化 left，right，window，result
while("右指针没有到结尾"){
    窗口扩大，加入right对应元素，更新当前window
    right++;(right右移，起到左闭右开的效果，[left,right))
    while("window不满足要求"){
        窗口缩小，移除left对应元素，left右移
    }
    更新最优结果result
}
返回result

寻找最短模板

初始化 left，right，window，result
while("右指针没有到结尾"){
    窗口扩大，加入right对应元素，更新当前window
    right++;(right右移，起到左闭右开的效果，[left,right))
    while("window满足要求"){
        更新最优结果result
        窗口缩小，移除left对应元素，left右移
    }
}
返回result