套用模板后，需要思考四个问题：

    1. 当right++时，即加入字符时，应该更新哪些数据？
    2. 什么条件下，窗口应该暂停扩大，left++，缩小窗口
    3. 当left++时，即移出字符时，应该更新哪些数据？
    4. 我们要的结果应该是在扩大窗口时更新还是缩小窗口时更新？
    1. //滑动窗口算法的大致逻辑
    3. int letf = 0, right = 0;
    4. while (right < s.size()) {
    5.     //增大窗口
    6.     window.add(s[right]);
    7.     right++;
    8.     while (window need shrink) {
    9.         //缩小窗口
    10.         window.remove(s[left]);
    11.         left++;
    12.     }
    13. }
    15. /*
    16. 其实困扰大家的，不是算法的思路，而是各种细节问题。
    17. 比如说如何向窗口中添加新元素，如何缩小窗口，在窗口滑动的哪个阶段更新结果。
    18. 即便你明白了这些细节，也容易出 bug，找 bug 还不知道怎么找，真的挺让人心烦的。
    19. */
    22. /* 滑动窗口算法框架 */
    23. void slidingWindow(String s, String t) {
    24.     Map<Character, Integer> need, window;
    25.     for (int i=0; i<t.length(); i++) {
    26.         need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
    27.     }
    29.     int left = 0, right = 0;
    30.     int valid = 0;
    31.     while (right < s.length()) {
    32.         // c是将移入窗口的字符
    33.         char c = s.charAt(right);
    34.         //右移窗口
    35.         right++;
    36.         //进行窗口数据的一系列更新
    37.         ...
    39.         /*debug输出的位置*/
    40.         System.out.print("window: " + left + ", " + right);
    42.         //判断左侧窗口是否要收缩
    43.         while (window need shrink) {
    44.             //d是将移出窗口的字符
    45.             char d = s.charAt(left);
    46.             //左移窗口
    47.             left++;
    48.             //进行窗口数据的一系列更新
    49.             ...
    50.         }
    51.     }
    52. }

    Leetcode76题：最小覆盖子串，难度hard

    1. 暴力解法，超出时间限制，思路就是暴力穷举每个包含t的子串，判断长度

      1. class Solution {
      2.  public String minWindow(String s, String t) {
      3.      //暴力解法
      4.      String ans = "";
      5.      if (t.length() > s.length()) {
      6.          return ans;
      7.      }
      8.      for (int i=0; i<s.length(); i++) {
      9.          for (int j=i+1; j<=s.length(); j++) {
      10.              String ss = s.substring(i, j); //s[i:j]
      11.              Map<Character, Integer> map = new HashMap<>();
      12.              for (int m=0; m<ss.length(); m++) {
      13.                  map.put(ss.charAt(m), map.getOrDefault(ss.charAt(m), 0)+1);
      14.              } 
      15.              int k = 0;
      16.              for (; k<t.length(); k++) {
      17.                  if (!map.containsKey(t.charAt(k)) || map.get(t.charAt(k)) <= 0) {
      18.                      break;
      19.                  } else {
      20.                      map.put(t.charAt(k), map.get(t.charAt(k))-1);
      21.                  }
      22.              }
      23.              if (k == t.length()) {
      24.                  if (ans.length() == 0) {
      25.                      ans = ss;
      26.                  } else {
      27.                      ans = ans.length() > ss.length() ? ss : ans;
      28.                  }
      29.              }
      30.          }
      31.      }
      32.      return ans;
      33.  }
      34. }

    2. 滑动滑动窗口的思路

    • 使用双指针的左右指针技巧：left = right = 0; [left, right)为一个窗口。
    • 不断增加right指针扩大窗口，直到窗口中的字符串包含了T的所有字符。
    • 停止right++，开始left++，缩小窗口，直到窗口中的字符串不再符合要求。
    • 同时，每次增加left，就更新一轮结果。

    • 重复2，3步，直到right到达字符串s的尽头。

      1. public String minWindow(String s, String t) {
      2.   String ans = "";
      3.   Map<Character, Integer> need = new HashMap<>(); //需要包含字符和个数
      4.   Map<Character, Integer> window = new HashMap<>(); //窗口中的字符和个数
      5.   for (int i=0; i<t.length(); i++) {
      6.       need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
      7.   }
      8.   //左右指针
      9.   int left = 0, right = 0;
      10.   int valid = 0; //窗口中有效字符个数
      11.   while (right < s.length()) {
      12.       char c = s.charAt(right); //移入窗口的元素
      13.       right++;
      14.       //进行窗口内数据的一系列更新
      15.       if (need.containsKey(c)) {
      16.           window.put(c, map.getOrDefault(c, 0) + 1);
      17.           if (need.get(c).equals(window.get(c))) {
      18.               valid++;
      19.           }
      20.       }
      22.       //判断左侧是否收缩
      23.       while (valid == need.size()) {
      24.           if (ans.length() == 0) {
      25.               ans = s.substring(left, right);
      26.           } else {
      27.               ans = ans.length() > (right-left) ? s.substring(left, right) : ans;
      28.           }
      29.           //移除的字符
      30.           char d = s.charAt(left);
      31.           left++;
      32.           if (need.containsKey(d)) { //存在需要的map中
      33.               if (need.get(d).euqals(window.get(d))) //个数也和window中相等
      34.                   valid--;
      35.               window.put(d, map.getOrDefault(d, 0) - 1);
      36.           }
      37.       }
      38.       return ans;
      39.   }
      40. }

      Leetcode567题：字符串排列，难度medium

    Leetcode438题：找所有字母异位词，难度medium

    Leetcode3题：最长无重复子串，难度medium