滑动窗口题型总结

定长滑动窗口

维护定长为 k 的窗口即可，满足条件就记录

▶

code

int ans = INI; // INI为初始化,按题目来即可
for (int right = 0; right < nums.size(); right++){
    // code
    int left = i - k + 1;
    if (left < 0) continue;
    if (condition) 
        ans = ...;
}

不定长滑动窗口

主要类型有三类：求最长子数组，求最短子数组，求子数组个数

• 越短越合法/求最长/最大

  ▶

  code

  while (condition){
      // 离开窗口
  }
  ans = max(ans, i - left + 1);

• 越长越合法/求最短/最小

  ▶

  code

  while (condition){
      // 离开窗口
  }
  ans = min(ans, i - left + 1)；

求子数组个数

• 越短越合法

  考虑固定右窗口，当区间长 k 的窗口合法时，区间长为 k − 1 的窗口必定合法，可选窗口为 [left, right], [left + 1, right], ⋯, [right, right] ，共有 right − left + 1 个

  ▶

  code

  while (contition){
      // 离开窗口
  }
  ans += right - left + 1;

• 越长越合法

  同理考虑固定右窗口， 当区间长 k 的窗口不合法时， 区间长为 k + 1 的窗口必定合法，可选窗口为 [left − 1, right], [left − 2, right], ⋯, [0, right]，共有 left 个

  注：[left, right]不合法，应关注 left − 1 的合法性

  ▶

  code

  while(condition){
      // 离开窗口
  }
  ans += left

• 恰好型

  例如：要计算有多少个元素和恰好等于 k，可以把问题拆分成 元素和 ≥ k 的子数组个数减去 元素和  ≥ k + 1 的子数组个数，也可以拆分成  ≤ k 减去  ≤ k − 1

  ▶

  code

  auto solve = [&](k) -> long long{
    int left = 0, ans = 0;
    for (auto &x : nums){
        // code
        while (condition){
            // 离开窗口
        }
        ans += left;
    }
    return ans;
  };
  ans = solve(k) - solve(k + 1);