滑动窗口

题目：

76. 最小覆盖子串（困难） (opens new window)

567. 字符串的排列（中等） (opens new window)

438. 找到字符串中所有字母异位词（中等） (opens new window)

3. 无重复字符的最长子串（中等） (opens new window)

思想：

• 1、我们在字符串 S 中使⽤双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为⼀个「窗⼝」。

• 2、我们先不断地增加 right 指针扩⼤窗⼝ [left, right)，直到窗⼝中的字符串符合要求（包含了 T 中 的所有字符）。

• 3、此时，我们停⽌增加 right，转⽽不断增加 left 指针缩⼩窗⼝ [left, right)，直到窗⼝中的字符串 不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新⼀轮结果。

• 4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

第 2 步相当于在寻找⼀个「可⾏解」，然后第 3 步在优化这个「可⾏解」，最终找到最优解。

最小覆盖字串

题目：

思想：

用两个指针left和right在s上滑动，记录一个左闭右开的滑动窗口。首先right向右滑动，直到窗口中包含t中所有字符，然后left向右滑动，同时更新结果（相当于开始优化我们之前的可行解），直到窗口中不包含t中所有字符。重复这个过程直到right到达s的末尾。

代码：

public class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> hs = new HashMap<>();
        HashMap<Character, Integer> ht = new HashMap<>();
        // 记录ht中各个元素出现了多少次
        for (int i = 0; i < t.length(); i++) {
            ht.put(t.charAt(i), ht.getOrDefault(t.charAt(i), 0) + 1);
        }
        int len = Integer.MAX_VALUE;
        String res = "";
        int count = 0;
        for (int i = 0, j = 0; i < s.length(); i++) {
            // 记录hs中各个元素出现了多少次
            hs.put(s.charAt(i), hs.getOrDefault(s.charAt(i), 0) + 1);
            if (ht.containsKey(s.charAt(i)) && ht.get(s.charAt(i)) >= hs.get(s.charAt(i))) {
                count++;
            }
            while(j < i && (!ht.containsKey(s.charAt(j)) || ht.get(s.charAt(j)) < hs.get(s.charAt(j)))) {
                hs.put(s.charAt(j), hs.get(s.charAt(j)) - 1);
                j++;
            }
            if(count == t.length() && i - j + 1 < len) {
                len = i - j + 1;
                res = s.substring(j, i + 1);
            }
        }
        return res;
    }
}

字符串的排列

题目：

思想：

代码：

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

无重复字符的最长字串

参考

https://leetcode-cn.com/problems/minimum-window-substring/solution/leetcode-76-zui-xiao-fu-gai-zi-chuan-cja-lmqz/

https://labuladong.gitee.io/algo/1/11/