滑动窗口法

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

以经典题为例：(力扣链接🔗)

滑动窗口 - 图1

暴力解法:

使用两次for循环即可，然后不断的寻找符合条件的子序列，时间复杂度很明显是滑动窗口 - 图2#card=math&code=O%28n%5E2%29&id=Lg2lP)。

  1. class Solution {
  2. public:
  3.     int minSubArrayLen(int s, vector<int>& nums) {
  4.         int result = INT32_MAX; // 最终的结果
  5.         int sum = 0; // 子序列的数值之和
  6.         int subLength = 0; // 子序列的长度
  7.         for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
  8.             sum = 0;
  9.             for (int j = i; j < nums.size(); j++) { // 设置子序列终止位置为j
  10.                 sum += nums[j];
  11.                 if (sum >= s) { // 一旦发现子序列和超过了s，更新result
  12.                     subLength = j - i + 1; // 取子序列的长度
  13.                     result = result < subLength ? result : subLength;
  14.                     break; // 因为我们是找符合条件最短的子序列，所以一旦符合条件就break
  15.                 }
  16.             }
  17.         }
  18.         // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
  19.         return result == INT32_MAX ? 0 : result;
  20.     }
  21. };

滑动窗口法:

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将滑动窗口 - 图3#card=math&code=O%28n%5E2%29&id=dAC46)的暴力解法降为滑动窗口 - 图4#card=math&code=O%28n%29&id=bXs6s)。

滑动窗口 - 图5

详细动图解析

  1. class Solution {
  2.     public int minSubArrayLen(int target, int[] nums) {
  3.         int left = 0, right = 0, sum = 0, result = Integer.MAX_VALUE;
  4.         for (; right < nums.length; right++) {
  5.             sum += nums[right];
  6.             // 如果大于则进行移动滑动窗口
  7.             while (sum >= target) {
  8.                 // 取最小序列的长度
  9.                 result = Math.min(result, right - left + 1);
  10.                 // 移动滑动窗口
  11.                 sum -= nums[left++];
  12.             }
  13.         }
  14.         return result == Integer.MAX_VALUE ? 0 : result;
  15.     }
  16. }

相关题目

水果成篮

题目描述（力扣链接）

滑动窗口 - 图6

解题方法

使用哈希表来判断是否重复，使用滑动窗口来更新范围。

  1. class Solution {
  2.     public int totalFruit(int[] fruits) {
  3.         // 使用hashMap判断是否重复
  4.         HashMap<Integer, Integer> map = new HashMap<>();
  5.         int right = 0, left = 0, result = 0;
  6.         for (; right < fruits.length; right++) {
  7.             // 将遍历的元素放入map中
  8.             map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);
  9.             // 如果其中map的长度超过三，则滑动窗口
  10.             while (map.size() > 2) {
  11.                 // 将left的取值减一
  12.                 map.put(fruits[left], map.get(fruits[left]) - 1);
  13.                 // 如果left的数量为0之后，则直接清除
  14.                 if (map.get(fruits[left]) == 0) map.remove(fruits[left]);
  15.                 left++;
  16.             }
  17.             // 获取其中取得最大的范围
  18.             result = Math.max(result, right - left + 1);
  19.         }
  20.         return result;
  21.     }
  22. }

最小覆盖子串

题目描述（力扣链接）

滑动窗口 - 图7

解题方法:

使用2个哈希表分别记录2个字符串中得词频情况进行判断，使用left和right两个指针在左闭右开的区间进行滑动，当包含t中所有的字符时停止滑动，进行判断，更新结果，再继续进行滑动。

  1. class Solution {
  2.     public String minWindow(String s, String t) {
  3.         // 记录窗口中的词频数量
  4.         HashMap<Character, Integer> window = new HashMap<>();
  5.         // 记录t中的所有字符，用来查询是否存在
  6.         HashMap<Character, Integer> map = new HashMap<>();
  7.         // count为s中包含t字符的个数，result为最小字符串的大小, start记录最小字符串开始的位置
  8.         int left = 0, right = 0, count = 0, result = Integer.MAX_VALUE, start = 0;
  9.         // 将t中的字符串全部放入map中
  10.         for (int i = 0; i < t.length(); i++) {
  11.             map.put(t.charAt(i), map.getOrDefault(t.charAt(i), 0) + 1);
  12.         }
  14.         // 循环进行判断
  15.         while (right < s.length()) {
  16.             // 如果map中含有该字符，将字符的value值加一，并且将count加一
  17.             if (map.containsKey(s.charAt(right))) {
  18.                 window.put(s.charAt(right), window.getOrDefault(s.charAt(right), 0) + 1);
  19.                 if (map.get(s.charAt(right)).equals(window.get(s.charAt(right)))) {
  20.                     count++;
  21.                 }
  22.             }
  24.             // 移动窗口右侧进行遍历
  25.             right++;
  27.             // 当计数器等于t的大小时，此时窗口需要移动
  28.             while (count == map.size()) {
  29.                 // 如果窗口大小小于上一个窗口的大小，进行赋值
  30.                 if (right - left < result) {
  31.                     result = right - left;
  32.                     start = left;
  33.                 }
  35.                 // 移动窗口
  36.                 if (map.containsKey(s.charAt(left))) {
  37.                     // 如果window中的值和map中的值数量相等才是包含t的字串
  38.                     if (window.get(s.charAt(left)).equals(map.get(s.charAt(left)))) {
  39.                         count--;
  40.                     }
  41.                     // 将窗口中保存值的数量减一
  42.                     window.put(s.charAt(left), window.getOrDefault(s.charAt(left), 0) - 1);
  43.                 }
  44.                 left++;
  45.             }
  46.         }
  48.         return result == Integer.MAX_VALUE ? "" : s.substring(start, start + result);
  49.     }
  50. }

固定长度的滑动窗口

找到字符串中所有字母异位词

详细见此链接题三
https://www.yuque.com/jugelizi-rxt6d/dqbihl/nm3gl3

滑动窗口的12种模板

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/yi-ge-mo-ban-miao-sha-10dao-zhong-deng-n-sb0x/