滑动窗口

需要注意的点

链表、子串、数组题，一般使用双指针做题。
双指针分为三种：快慢指针，左右指针，滑动窗口
快慢指针：针对链表操作，归并排序，找重点，链表成环
左右指针：最为常见，应用于反转数组，二分搜索
滑动窗口：子串问题，左右指针滑动窗口

滑动窗口算法：

int left = 0, right = 0;

while (right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;
    
    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

重难点：

如何向窗口中添加新元素
如何缩小窗口
在窗口更新的哪个阶段更新结果。

算法框架：

public void slidingWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }
    
    int left = 0, right = 0;
    int valid = 0;
    while (right < s.length()) {
        
        // c是将移入窗口的字符
        char c = s.charAt(right);
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        。。。。
            
        // debug 输出的位置
        System.out.format("windows: [%d, %d)", left, right);
        // 判断左侧窗口是否要收缩
        while(window needs shrink) {
            // d是将移出窗口的字符
            char d = s.charAt(left);
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            .....
        }
    }
}

滑动窗口算法题需要将考虑的四个主要问题：

将移动right扩大串口，即加入字符时，应该更新哪些数据？
什么条件下，窗口应该暂停扩大，开始移动left缩小窗口？
当移动 left 缩小窗口，即移出字符时，应该更新哪些数据？
我们要的结果应该在扩大窗口时还是在缩小窗口时进行更新？

leetcode 76 java:

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0) {
            return "";
        }
 
        Map<Character, Integer> need = new HashMap<Character, Integer>();
        Map<Character, Integer> window = new HashMap<Character, Integer>();
 
        for (char c : t.toCharArray()) {
            int count = need.getOrDefault(c, 0);
            need.put(c, count + 1);
        }
        // Left and Right pointer
        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(c)) {
                int tempCount = window.getOrDefault(c, 0);
                window.put(c, tempCount + 1);
                if (window.get(c) == need.get(c)) {
                    valid++;
                }
            }
 
            // 判断左侧窗口是否要收缩
            while (valid == need.size()) {
                // while (need.size().equals(valid)) {
                // 在这里更新最小覆盖子串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
 
                // d 是将移出窗口的字符
                char d = s.charAt(left);
                // 缩小窗口
                left++;
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d) == need.get(d)) {
                        valid--;
                    }
                    int tempCount = window.get(d);
                    window.put(d, tempCount - 1);
                }
            }
        }
 
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

能够通过leetcode的代码：

public String minWindow(String s, String t) {
        int[] counts = new int[100];

        // 构建need
        for (char c : t.toCharArray()) {
            counts[c - 'A']++;
        }
        char[] cs = s.toCharArray();

        int num = t.length(), pre = 0, ans = cs.length + 1, pos = 0, len = cs.length;
//        int num = t.length(), pre = 0, ans = cs.length + 1, pos = 0, len = cs.length;

        for (int i = 0; i < len; ++i) {
            if (--counts[cs[i] - 'A'] >= 0) {
                num--;
            }

            while (pre < len && counts[cs[pre] - 'A'] < 0) {
                counts[cs[pre++] - 'A']++;
            }
            if (num == 0 && i - pre + 1 < ans) {
                ans = i - pre + 1;
                pos = pre;
            }
        }

        return ans == cs.length + 1? "" : s.substring(pos, pos + ans);
    }

leetcode 567 java解法：

public Boolean checkInclusion(String s, String t) {
        if (s.length() == 0 || t.length() == 0) {
            return false;
        }
        /*判断s中是否存在t的排列*/
        Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
        for (char c: t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

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

        while (right < s.length()) {
            char c = s.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 (right - left >= t.length()) {
                // 在这里判断是否找到了合法的子串
                if (valid == need.size()) {
                    return true;
                }
                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.getOrDefault(d, 0) - 1);
                }
            }
        }

        return false;
    }