滑动窗口

定义

在一个数组中框定一段子数组作为窗口

若想让该窗口元素增加，可以考虑让右边界r++，即窗口从右边吸收数字

若想让该窗口元素减少，可以考虑让左边界l++，即窗口从左边弹出数字

一般解决子数组相关问题

例1/模板

给定一个含有\(n\)个正整数的数组和一个正整数target

找到累加和\(\geq\)target的长度最小的子数组并返回长度，如果不存在符合条件的则返回0

我们可以先固定子数组的左端点，让右端点右移，直到数组和大于target，由于数组所有数都为正整数，因此找到第一个累加和大于target后，后面再加一定也大于target

此时循环判断累加和是否\(\geq\)target，若成立则剔出左侧数字，记录子数组长度

然后以该子数组为起点，右端点右移，重复上述操作，寻找等于target的子数组，记录数组长度

时间复杂度：\(O(n)\)

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
int n,tar;
int a[N];

int main()
{
  ios
  cin >> n >> tar;
  for (int i = 1;i<=n;i++){
    cin >> a[i];
  }
  int ans = 0x3f3f3f3f, sum = 0, l = 0; // 定义记录结果长度，数组元素之和，左端点
  for (int r = 1;r<=n;r++){ // 先让右端点右移
    sum+=a[r]; // 累加求和
    while(sum>=tar){ // 当求和大于等于目标开始移动左端点以寻找更小区间
      ans = min(ans,r-l+1); // 更新最小区间
      sum-=a[l++]; // 减去滑出窗口的数同时让左端点右移
    }
  }
  // 找到符合目标的区间
  if (ans<=n) cout << ans;
  else cout << 0 ;
  return 0;
}

例2

给定一个字符串\(s\)，找出不含有重复字符的最长字串长度

即寻找最长无重复字符的窗口

让右边界一直右移，直到遇到重复字符，让左边界移动到max(左边界，重复字符上次位置+1)

因为任何时候窗口情况一定是没有重复数组在内的，若重复字符上次位置比此时左边界小，则若还是移动到重复字符上次位置+1的话，窗口会变长，不保证加长部分会不会又出现重复字符

若右移后无重复字符，可以看作重复字符位置为-1或不存在，用max仍保持原左边界

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
string s;
unordered_map<char,int> cnt;
int main()
{
  ios
  cin >> s;
  for (int i = 0;i<s.size();i++) cnt[s[i]]=-1; // 初始化都为第一次出现
  int ans = 0; // 记录最长区间
  for (int l = 0, r = 0;r<s.size();r++){
    l = max(l,cnt[s[r]]+1); // 左边界移动
    ans = max(ans,r-l+1); // 记录结果
    cnt[s[r]]=r; // 更新上次出现字符位置为当前r位置
  }
  cout << ans;
  
  return 0;
}

例3

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

我们可以逆向以一种”debt”思维解决。遍历要查找的字符，发现一个-1，这样需要查找的字符数都为负数，在查找时，每个字符出现后对应加一，则非要查找字符将始终为正数，而要查找的字符为负数

先让右边界右移，当debt变为0（窗口包含了足够要查找的字串），开始移动左边界，使字串最小，这时debt大于0的都为不需要查找的字符，故可以左移，直到碰到需要查找的不再移动。

#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
const int N = 2e5 + 10;
const double pi = acos(-1.0);
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const double eps = 1e-6;
string s,t;
unordered_map<char,int> cnt;
int main()
{
  ios
  cin >> s >> t;
  if (s.size()<t.size()){
    cout << "";
    return 0;
  }
  for (int i = 0;i<t.size();i++) cnt[t[i]]--;
  int len = INF, start = 0; // len用于记录最小字串，start记录字串开头，便于输出
  int debt = t.size();
  for (int l = 0, r = 0;r<s.size();r++){
    if (cnt[s[r]]++<0) debt--; // 字符计数加一后仍是负的，证明是要查找的(debt的)字符，让debt--
    if(debt==0){ // 所有字符都查到后
      while(cnt[s[l]]>0){ // 寻找最小子区间
        cnt[s[l++]]--; // 若是非查找字符，可以让左边界右移拿回
      }
      if (r-l+1<len){ // 记录最小子区间以及开始位置
        len = r-l+1;
        start = l;
      }
    }
  }
  // 若查不到则输出空字符串，否则截取字符串输出
  len == INF ? cout <<"" : cout << s.substr(start,start+len);
  return 0;
}

总结

关键：找到范围和答案指标之间的单调性关系

求解大流程：求子数组在每个位置开头或结尾情况下的答案

红魔咖啡馆

【算法】滑动窗口

滑动窗口

定义

例1/模板

例2

例3

总结