Leetcode---6.滑动窗口篇


滑动窗口算法框架

点击查看代码
void slidingWindow(string s, string t) {
    unordered_map need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}
其中两处 ... 表示的更新窗口数据的地方

一、最小覆盖子串

现在开始套模板,只需要思考以下四个问题:
1、当移动 right 扩大窗口,即加入字符时,应该更新哪些数据?
2、什么条件下,窗口应该暂停扩大,开始移动 left 缩小窗口?
3、当移动 left 缩小窗口,即移出字符时,应该更新哪些数据?
4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新?

点击查看代码
    public String minWindow(String s, String t) {
        // 统计字符串t的词频
        Map need = new HashMap<>();
        for (Character c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        // 记录滑动窗口的词频
        Map window = new HashMap<>();
        // 记录当前窗口中有多少个字符已经满足要求
        int valid = 0;
        // 记录最小覆盖子串中的起始位置和长度
        int start = 0, len = Integer.MAX_VALUE;
        // 开始滑动窗口(左闭右开)
        int left = 0;
        int right = 0;
        while (right < s.length()) {
            // c是将移入窗口的字符
            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 (valid == need.size()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d是将移除窗口的字符
                char d = s.charAt(left);
                // 右移窗口
                left++;
                // 进行窗口内数据的一系列更新
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }

            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }

二、字符串排列

三、找所有字母异位词

四、最长无重复子串

参考链接:
【1】我写了首诗,把滑动窗口算法算法变成了默写题 :: labuladong的算法小抄

相关