滑动窗口

1. 总述

滑动窗口解题逻辑比较清晰，一般需要维护两个map，一个用于初始化已知的子串，另一个用作窗口，步骤如下：

• 扩大窗口（注意扩大窗口的条件）
• 窗口内数据更新（window窗口）
• 缩小窗口 （注意缩小窗口的条件）
• 窗口内数据更新

2. 以LeetCode76 最小覆盖子串为例

public String minWindow(String s, String t) {
        HashMap<String, Integer> need = new HashMap<>();
        HashMap<String, Integer> window = new HashMap<>();

        for (char c : t.toCharArray()) {
            need.put(String.valueOf(c), 1);
        }

        int left = 0, right = 0;
        int valid = 0;

        // 记录最小覆盖子串的起始索引及长度
        int start = 0, len = Integer.MAX_VALUE;

        while (right < s.length()) {
            // c 是将移入窗口的字符
            char c = s.charAt(right);
            // 扩大窗口
            right++;
            // 进行窗口内数据的一系列更新
            if (need.containsKey(String.valueOf(c))) {
                window.put(String.valueOf(c), window.getOrDefault(c, 0) + 1);
                if (window.get(String.valueOf(c)).equals(need.get(String.valueOf(c)))) {
                    valid++;
                }
            }

            // 判断左侧窗口是否要收缩
            while (valid == need.size()) {
                // 在这里更新最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d 是将移出窗口的字符
                char d = s.charAt(left);
                // 缩小窗口
                left++;
                // 进行窗口内数据的一系列更新
                if (need.containsKey(String.valueOf(d))) {
                    if (window.get(String.valueOf(d)).equals(need.get(String.valueOf(d)))) {
                        valid--;
                    }
                    window.put(String.valueOf(d), window.get(String.valueOf(d)) - 1);
                }

            }
        }
        // 返回最小覆盖子串
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);

    }