思路和模板

算法步骤
1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求。（得到可行解）
3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求。同时，每次增加 left，我们都要更新一轮结果。（优化可行解）
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

例题

76. 最小覆盖字串

套模板，滑动窗口的向右扩张与左侧收缩。

  1. class Solution {
  2.     public String minWindow(String s, String t) {
  3.         // 需要的字符和窗口中的字符
  4.         Map<Character, Integer> need = new HashMap<>();
  5.         Map<Character, Integer> window = new HashMap<>();
  6.         // 填充need字典，包含了需要的char和个数
  7.         int tLength = t.length();
  8.         for (int i = 0; i < tLength; ++i) 
  9.             need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
  10.         // 滑动窗口 [left, right)
  11.         int left = 0, right = 0;
  12.         // 记录满足need条件的char个数，当valid = need.size则满足条件
  13.         int valid = 0;
  14.         int sLength = s.length();
  15.         int start = 0, end = Integer.MAX_VALUE;
  16.         while (right < sLength) {
  17.             char c = s.charAt(right++);
  18.             // c进入窗口
  19.             if (need.containsKey(c)) {
  20.                 window.put(c, window.getOrDefault(c, 0) + 1);
  21.                 if (window.get(c).equals(need.get(c))) valid++;
  22.             }
  23.             // 当符合条件，则将窗口左侧收缩。跳出后已经不满足且已经得到了当前的最小范围，
  24.             while (valid == need.size()) {
  25.                 // 收缩前更新一下结果
  26.                 if (right - left < end - start) {
  27.                     end = right;
  28.                     start = left;
  29.                 }
  30.                 char d = s.charAt(left++);
  31.                 if (need.containsKey(d)) {
  32.                     if (window.get(d).equals(need.get(d))) valid--;
  33.                     window.put(d, window.get(d) - 1);
  34.                 }
  35.             }
  36.         }
  37.         return (start == 0 && end == Integer.MAX_VALUE) ? "" : s.substring(start, end);
  38.     }
  39. }

567. 字符串的排列

  1. class Solution {
  2.     public boolean checkInclusion(String s1, String s2) {
  3.         Map<Character, Integer> window = new HashMap<>();
  4.         Map<Character, Integer> need = new HashMap<>();
  5.         // [left, right)
  6.         int left = 0, right = 0;
  7.         int len1 = s1.length(), len2 = s2.length();
  8.         int valid = 0;
  10.         // Initialize need
  11.         for (int i = 0; i < len1; ++i) 
  12.             need.put(s1.charAt(i), need.getOrDefault(s1.charAt(i), 0) + 1);
  13.         while (right <  len2) {
  14.             char c = s2.charAt(right++);
  15.             window.put(c, window.getOrDefault(c, 0) + 1);
  16.             if (need.getOrDefault(c, 0).equals(window.get(c))) valid++;
  17.             // 当窗口大小达到s1的长度才可能包括s1的排列，才可以开始left收缩
  18.             while (right - left >= len1) {
  19.                 //System.out.println(need + "\n" + window + "\n" + valid + " " + len1);
  20.                 // 得到结果马上返回
  21.                 if (valid == need.size()) return true;
  22.                 // 向左收缩，考虑后果
  23.                 char d = s2.charAt(left++);
  24.                 if (need.containsKey(d)) {
  25.                     if (need.get(d).equals(window.get(d))) valid--;
  26.                     window.put(d, window.get(d) - 1);
  27.                 }
  28.             }
  29.         }
  30.         return false;
  31.     }
  32. }

438. 找所有字母异位词

  1. class Solution {
  2.     public List<Integer> findAnagrams(String s, String p) {
  3.         Map<Character, Integer> window = new HashMap<>();
  4.         Map<Character, Integer> need = new HashMap<>();
  5.         List<Integer> result = new ArrayList<>();
  6.         int valid = 0;
  7.         int left = 0, right = 0;
  8.         int len1 = s.length(), len2 = p.length();
  10.         for (int i = 0; i < len2; ++i) 
  11.             need.put(p.charAt(i), need.getOrDefault(p.charAt(i), 0) + 1);
  12.         while (right < len1) {
  13.             char c = s.charAt(right++);
  14.             window.put(c, window.getOrDefault(c, 0) + 1);
  15.             if (window.get(c).equals(need.getOrDefault(c, 0))) valid++;
  17.             while (right - left >= len2) {
  18.                 if (valid == need.size()) result.add(left);
  19.                 char d = s.charAt(left++);
  20.                 if (need.containsKey(d)) {
  21.                     if (window.get(d).equals(need.get(d))) valid--;
  22.                     window.put(d, window.get(d) - 1);
  23.                 }
  24.             }
  25.         }
  26.         return result;
  27.     }
  28. }

和上面那题就基本一样。思考：既然是用map，那就无法考虑按顺序排列的问题了。

3.无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> window = new HashMap<>();
        int left = 0, right = 0;
        int len = s.length();
        int result = 0;

        while (right < len) {
            char c = s.charAt(right++);
            window.put(c, window.getOrDefault(c, 0) + 1);

            // 算最大值，所以缩完再更新
            while (window.get(c) > 1) {
                char d = s.charAt(left++);
                window.put(d, window.get(d) - 1);
            }
            result = Math.max(right - left, result);
        }
        return result;
    }
}