滑动窗口

76. 最小覆盖子串

567. 字符串的排列

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

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

记得一定要看到文末，会有惊喜哦哦哦哦！！！

滑动窗口是为了解决字符串中子串相关问题，举几个例子：

• s = "ADOBECODEBANC", t = "ABC"，寻找s中最小的t覆盖，结果为：BANC
• s1 = "ab" s2 = "eidbaooo"，判断s2中是否包含s1的任一全排列序列
• s = "cbaebabacd", p = "abc"，寻找s中p的所有全排列
• s = "abcabcbb"，寻找s中最长无重复子串

上述四个例子分别对应最上面的四个题目，详情可点击题目查看

我们的思路很简单：维护一个窗口window，不断的对窗口进行扩张和收缩，来得到最终的结果。我们接下来针对第一个例子来详细介绍滑动窗口的思想

首先我们利用左右指针来模拟一个窗口，窗口的大小为[left, right)，注意是左闭右开

其次我们还需要一个存放我们目标结果的窗口need，只有当window==need的时候，才进行一次结果的更新；既然need是存放目标结果的窗口，那么need始终都不会发生改变

同时我们维护了一个valid变量，根据题意，只有当valid满足相应的条件时，才进行窗口的收缩

如上面的动图所示。下面给出相对于的代码 (建议仔细看注释)。题目最小覆盖子串

public String minWindow(String s, String t) {
    // 实时记录窗口内的数据 (只存放 need 中需要的字符)
    Map<Character, Integer> window = new HashMap<>();
    // 记录目标字符，始终保持不变
    Map<Character, Integer> need = new HashMap<>();
    // 初始化 need
    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }
    int left = 0, right = 0;
    // 窗口中满足 need 目标需要的字符个数
    // 即：valid == need.size() 时满足条件
    int valid = 0;
    // 记录最小覆盖的起始位置及长度
    int start = 0, len = Integer.MAX_VALUE;
    while (right < s.length()) {
        // 1. 窗口扩张
        char c = s.charAt(right);
        right++;
        // 2. 更新 valid，window 数据
        // 判断此时窗口当前数据是否为 need 需要的数据，即 need 中是否存在
        if (need.containsKey(c)) {
            // 先更新 window
            window.put(c, window.getOrDefault(c, 0) + 1);
            // 后更新 valid
            // 说明字符 c 的数量已经满足要求
            if (window.get(c).equals(need.get(c))) {
                valid++;
            }
        }
        // 当 valid == need.size() 时，窗口开始收缩
        while (valid == need.size()) {
            // 1. 判断结果是否需要更新
            if (right - left < len) {
                start = left;
                len = right - left;
            }
            // 2. 窗口收缩
            char d = s.charAt(left);
            left++;
            // 3. 更新 valid，window 数据
            if (need.containsKey(d)) {
                // 先更新 valid
                // 如果窗口内字符 d 的数量和 need 中一样，valid--
                // 原因：更新后字符 d 的数量已经不满足要求，所以 valid 需要 -1
                // 小技巧：判断 valid++ 和 valid-- 的条件是一样的
                if (window.get(d).equals(need.get(d))) {
                    valid--;
                }
                // 后更新 window
                window.put(d, window.get(d) - 1);
            }
        }
    }
    return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}

题目 字符串的排列

xxxxxxxxxx
public boolean checkInclusion(String s1, String s2) {
    Map<Character, Integer> window = new HashMap<>();
    Map<Character, Integer> need = new HashMap<>();
    for (char c : s1.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);
    int left = 0, right = 0;
    int valid = 0;
    while (right < s2.length()) {
        char c = s2.charAt(right);
        right++;
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) valid++;
        }
        while (valid == need.size()) {
            // 先判断，后收缩
            // 如果窗口长度等于 s1 长度，则满足条件
            if (right - left == s1.length()) return true;
            // 否则，进行收缩
            char d = s2.charAt(left);
            left++;
            // 收缩后，更新 valid，window 数据
            if (need.containsKey(d)) {
                // 先更新 valid
                if (window.get(d).equals(need.get(d))) valid--;
                // 后更新 window
                window.put(d, window.get(d) - 1);
            }
        }
    }
    return false;
}

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

xxxxxxxxxx
public List<Integer> findAnagrams(String s, String p) {
    Map<Character, Integer> window = new HashMap<>();
    Map<Character, Integer> need = new HashMap<>();
    // 初始化 need
    for (char c : p.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);
    int left = 0, right = 0;
    int valid = 0;
    List<Integer> res = new ArrayList<>();
    while (right < s.length()) {
        char c = s.charAt(right);
        right++;
        // 更新 valid，window 数据
        // 只有当 need 中存在时，才更新
        // 记住：window 记录 need 需要的数据
        if (need.containsKey(c)) {
            // 先更新 window，再更新 valid，和收缩刚好相反
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) valid++;
        }
        while (valid == need.size()) {
            // 先判断
            if (right - left == p.length()) res.add(left);
            // 后收缩
            char d = s.charAt(left);
            left++;
            // 更新 valid，window 数据
            // 只有当 need 中存在时，才更新
            // 记住：window 记录 need 需要的数据
            if (need.containsKey(d)) {
                // 先更新 valid，再更新 window
                if (window.get(d).equals(need.get(d))) valid--;
                window.put(d, window.get(d) - 1);
            }
        }
    }
    return res;
}

题目 无重复字符的最长子串

注意：这个题目和模版有少许的区别，但是核心思想是不变的，只是少了need目标窗口而已。但是我尽量把代码和模版保持了一致

xxxxxxxxxx
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, right = 0;
    // true: 无重复
    // false: 有重复
    boolean valid = true;
    int res = 0;
    while (right < s.length()) {
        // 窗口扩张
        char c = s.charAt(right);
        right++;
        // 更新 window，valid
        window.put(c, window.getOrDefault(c, 0) + 1);
        if (window.get(c) > 1) {
            // 有重复
            valid = false;
        }
        // 有重复后，开始收缩窗口
        while (!valid) {
            char d = s.charAt(left);
            left++;
            // 更新 valid 的条件和扩张时的条件保持一致
            if (window.get(d) > 1) {
                valid = true;
            }
            // 更新 window
            window.put(d, window.get(d) - 1);
        }
        // 执行到此处，一定无重复
        // 更新结果
        res = Math.max(res, right - left);
    }
    return res;
}

好了，现在来总结一下模版吧！！哈哈哈哈哈

xxxxxxxxxx
public String slideWindow(String s, String t) {
    // 实时记录窗口内的数据 (只存放 need 中需要的字符)
    Map<Character, Integer> window = new HashMap<>();
    // 记录目标字符，始终保持不变
    Map<Character, Integer> need = new HashMap<>();
    // 初始化 need 目标窗口
    // code...
    
    // 左闭右开 [left, right)
    int left = 0, right = 0;
    
    // 存放满足收缩条件的变量
    // valid
    
    while (right < s.length()) {
        // 1. 窗口扩张
        char c = s.charAt(right);
        right++;
        // 2. 更新 valid，window 数据
        if (need.containsKey(c)) {
            // 更新 window
            // code...
            
            // 更新 valid
            if (条件) {
                // code...
            }
        }
        // 根据 valid，来判断是否需要收缩
        while (valid == need.size()) {
            // 1. 判断结果是否需要更新
            // code...
            
            // 2. 窗口收缩
            char d = s.charAt(left);
            left++;
            // 3. 更新 valid，window 数据
            if (need.containsKey(d)) {
                // 更新 valid
                if (条件) {
                    // code...
                }
                
                // 后更新 window
                // code...
            }
        }
    }
    return res;
}