滑动窗口的目的在于节省时间复杂度。经典场景为，两层循环遍历从 [i, j]序列，可以通过滑动窗口将时间复杂度降为O(N)。
滑动窗口根据窗口长度是否固定，分为两种情况。变窗口用于求一些最大、最小子串问题；定窗口用于求一些是否有定长的子串满足条件等问题。

变窗口长度模板（以最小窗口为例）

用left标识即将移出窗口的下标，right标识即将移入窗口的下标，用两个HashMap，need和window来记录需要的条件和窗口内的情况。

  1. public static String minWindow(String s, String t) {
  2.     HashMap<Character, Integer> need = new HashMap<>();
  3.     int t_len = t.length();
  4.     for (int i = 0; i < t_len; i++) {
  5.         need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
  6.     }
  7.     // left为即将移出窗口的下标，right为即将移入窗口的下标，均初始化为0
  8.     int left = 0, right = 0;
  9.     int valid = 0;
  10.     // 记录最小覆盖子串的起始索引及⻓度
  11.     int start = 0, len = Integer.MAX_VALUE;
  13.     // 先右移right直到满足条件，循环条件为 right<s.length
  14.     while (right < s.length()) {
  15.         // c 是将移入窗口的字符
  16.         char c = s.charAt(right); 
  17.         // 右移窗口
  18.         right++;
  19.         // 进行窗口内数据的一系列更新
  20.         ...
  21.         // 判断左侧窗口是否要收缩，一般条件是看window是否满足了need的要求
  22.         while (...) {
  23.             // d 是将移出窗口的字符
  24.             char d = s.charAt(left);
  25.             // 左移窗口
  26.             left++;
  27.             // 进行窗口内数据的一系列更新
  28.             ...
  29.             // 更新最优结果
  30.         }
  31.     }
  33.     return ...;
  34. }

定窗口长度模板

基本组成与结构与变窗口的模板一致，区别在于左窗口移动的条件变化

  1. public static boolean checkInclusion(String s, String t) {
  2.     HashMap<Character, Integer> need = new HashMap<>();
  3.     HashMap<Character, Integer> window = new HashMap<>();
  4.     int t_len = t.length();
  5.     for (int i = 0; i < t_len; i++) {
  6.         need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
  7.     }
  8.     int left = 0, right = 0;
  9.     int valid = 0;
  10.     // 记录最小覆盖子串的起始索引及⻓度
  11.     int start = 0, len = Integer.MAX_VALUE;
  12.     while (right < s.length()) {
  13.         // c 是将移入窗口的字符
  14.         char c = s.charAt(right); 
  15.         // 右移窗口
  16.         right++;
  17.         // 进行窗口内数据的一系列更新
  18.         if (need.containsKey(c)) {
  19.             int tmp = window.getOrDefault(c, 0);
  20.             window.put(c, ++tmp);
  21.             if (window.get(c) == need.get(c))
  22.                 valid++;
  23.         }
  24.         // 判断左侧窗口是否要收缩，条件为right-left>=要求的长度
  25.         while (right-left>=t_len) {
  26.             // 变窗口长度更新结果的位置，改为了 只要发现满足条件的就直接返回true
  27.             if (valid==need.size()) {
  28.                 return true;
  29.             }
  30.             // d 是将移出窗口的字符
  31.             char d = s.charAt(left);
  32.             // 左移窗口
  33.             left++;
  34.             // 进行窗口内数据的一系列更新
  35.             if (need.containsKey(d)) {
  36.                 if (window.get(d) == need.get(d))
  37.                     valid--;
  38.                 int tmp = window.get(d);
  39.                 window.put(d, --tmp);
  40.             }
  41.         }
  42.     }
  43. // 返回最小覆盖子串
  44.     return false;
  45. }

例子1：定长的滑动窗口。187. 重复的DNA序列
一般的方法是使用一层循环O(N)遍历开始元素的位置，在循环用substring()得到子串O(L)，记录在map中O(1)，并且检查map对应key的值是否为2，是则说明重复，添加到结果集中。因为每次循环内都用了substring()，耗费O(L)的时间并创建一个占用O(L)空间的新字符串，因此整体的时间复杂度为O(NL)，空间复杂度为O(NL)。
改进可以从空间与时间两个维度。空间方面，想办法找个方案替代substring()，节省占用的空间，需要一种新的表示子串的方法。由于DNA序列中的字符只有4种，可以使用一个2位的二进制数表示，则一个长L的子串可以用一个2*L位的二进制数表示，即可以用一个int/ long表示，空间占用O(1)。
时间方面，如果用int的二进制位表示子串，则每次循环内，计算子串的int值仍然需要循环L次。由于前一个子串与后一个子串只有头尾不一样，此时可以使用滑动窗口节省时间复杂度，只需要在窗口移动时更新头尾改变导致的子串int值变化，时间占用O(1)。

  1. class Solution {
  2.     static final int L = 10;
  3.     // 使用 2位二进制数表示4种可能字符
  4.     Map<Character, Integer> bin = new HashMap<Character, Integer>() {{
  5.         put('A', 0);
  6.         put('C', 1);
  7.         put('G', 2);
  8.         put('T', 3);
  9.     }};
  11.     public List<String> findRepeatedDnaSequences(String s) {
  12.         List<String> ans = new ArrayList<String>();
  13.         int n = s.length();
  14.         if (n <= L) {
  15.             return ans;
  16.         }
  17.         // 使用20位二进制数 x 表示一个子串
  18.         int x = 0;
  20.         // 初始化窗口一开始对应的 x 值
  21.         for (int i = 0; i < L - 1; ++i) {
  22.             x = (x << 2) | bin.get(s.charAt(i));
  23.         }
  24.         Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
  25.         for (int i = 0; i <= n - L; ++i) {
  26.             // 窗口滑动时，更新子串对应的 x 值
  27.             x = ((x << 2) | bin.get(s.charAt(i + L - 1))) & ((1 << (L * 2)) - 1);
  28.             cnt.put(x, cnt.getOrDefault(x, 0) + 1);
  29.             if (cnt.get(x) == 2) {
  30.                 ans.add(s.substring(i, i + L));
  31.             }
  32.         }
  33.         return ans;
  34.     }
  35. }