滑动窗口算法（思想）

算法简介 滑动窗口，顾名思义，就是有一个大小可变的窗口，左右两端方向一致的向前滑动（右端固定，左端滑动；左端固定，右端滑动）。

可以想象成队列，一端在push元素，另一端在pop元素，如下所示： 假设有数组[a b c d e f g h] 一个大小为3的滑动窗口在其上滑动，则有: [a b c] [b c d] [c d e] [d e f] [e f g] [f g h] 适用范围 1、一般是字符串或者列表 2、一般是要求最值（最大长度，最短长度等等）或者子序列 算法思想 1、在序列中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个窗口。 2、先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的序列符合要求。 3、此时，停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的序列不再符合要求。同时，每次增加 left前，都要更新一轮结果。 4、重复第 2 和第 3 步，直到 right 到达序列的尽头。 思路其实很简单：第 2 步相当于在寻找一个可行解，然后第 3 步在优化这个可行解，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

以上内容来自：

又名尺取法，根据不同类型可以有窗口大小固定的，和可变的。滑动窗口算法可以用以解决数组/字符串的子元素问题，它可以将嵌套的循环问题，转换为单循环问题，降低时间复杂度。

简单实例：

洛谷P1614

输入格式

第一行有两个用空格隔开的整数，分别代表 n和 m。

第 2 到第 (n + 1)行，每行一个整数，第 (i + 1) 行的整数代表第i件事的值 。

输出格式

输出一行一个整数，表示连续 m个值的和的最小值是多少。

输入输出样例

输入

8 3

1

4

7

3

1

2

4

3 输出 6

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int m,n,t;
    cin>>n>>m;
    vector<int>s;
    for(int i=0;i<n;i++)
    {
        cin>>t;
        s.push_back(t);
    }
    int minsum=0;
    for(int i=0;i<m;i++)
    {
        minsum+=s[i];
    }
    int winsum=minsum;
    for(int i=m;i<n;i++)
    {
        winsum+=s[i]-s[i-m];
        if(minsum>winsum)
            minsum=winsum;        
    }
    cout<<minsum;
    return 0;
}