聊聊算法——滑动窗口

标签：keyword   length   ima   abc   调度系统   ddc   red   instr   title   

有看到一句话，我深以为然：“所有算法的终极数据结构只有两种：数组和链表！”其他所有数据结构都是数组或链表的衍生品，

不管是树还是图或者栈，至于算法就最终都落到了这两种结构的操作上，滑动窗口也不例外！滑动窗口的应用场景还是很多的：

HTTP的帧传输，滑动窗口限流算法、Flink中的滑动窗口等，今天，我们就来聊聊滑动窗口的算法框架！

作者原创文章，谢绝一切转载，违者必究！

准备：

Idea2019.03/JDK11.0.4

难度： 新手--战士--老兵--大师

目标：

1. 滑动窗口算法分析与应用

1 算法框架

先给出滑动窗口算法框架：

/* 滑动窗口算法框架 */
private static void minWindow(String s,String t){
    // 滑动窗口左右侧位置指针
    int left = 0,right = 0;
    while (right         // 滑动窗口右边增加
        right ++;
        if ( 滑动窗口满足目标){
            //对窗口内元素操作 
        }
        // 滑动窗口左边缩小
        while ( 滑动窗口缩小条件 ){
            // 
            left ++;
        }
    }
}

我们以实际例子来加强理解，来个 hard 级别的玩一下，力扣第76题：

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串：

示例，输入: S = "ADOBECODEBANC", T = "ABC"，输出: "BANC"，如果不存在则返回空串。

先直接写出解法如下(Java)，略长，耐心看完必有收获：

public class SlideWindow {
    public static void main(String[] args) {
        String s = "DBABECFCAB";
        String t = "ABC";
        System.out.println(minWindow(s,t));
    }
    private static String minWindow(String s,String t){
        if (s.length()==0 || t.length() ==0){
            return "NULL";
        }
        // 目标字符串使用Map存储，如果有重复的，则数量累加
        Map dictT = new HashMap(8);
        for (int i = 0; i             int count = dictT.getOrDefault(t.charAt(i),0);
            dictT.put(t.charAt(i),count +1);
        }
        // 目标字符串的长度
        int required = dictT.size();
        // 滑动窗口左右侧位置指针
        int left = 0,right = 0;
        // 滑动窗口中字符串统计
        Map winStrMap = new HashMap(16);
        // 窗口内子串与目标串字符匹配的个数
        int formed = 0;
        // 记录最小窗口长度，{窗口长，left，right}
        int[] ans = {-1,0,0};
        //窗口进行滑动
        while (right             char c = s.charAt(right);
            int count = winStrMap.getOrDefault(c,0);
            winStrMap.put(c,count + 1);
            // 匹配一个字符则记录一次
            if (dictT.containsKey(c) && winStrMap.get(c).intValue() == dictT.get(c).intValue()){
                formed ++;
            }
            while (left                 c = s.charAt(left);
                //计算最小窗口长
                if( ans[0] == -1 || (right - left + 1 0])){
                    ans[0] = right - left + 1;
                    ans[1] = left;
                    ans[2] = right;
                }
                winStrMap.put(c, winStrMap.get(c) -1);
                if (dictT.containsKey(c) && winStrMap.get(c)                     formed --;
                }
                // 进行左侧缩小滑动
                left ++;
            }
            //窗口向右滑动
            right ++;
        }
        return ans[0] == -1 ? "NULL" : s.substring(ans[1],ans[2]+1);
    }
}

以上代码解释：使用两个Map分别记录目标字符串和滑动窗口内字符串的字符数量，并进行对比；在窗口向右滑动的过程中，

如果满足目标条件则停下来进行窗口左侧缩小滑动，并记录下可行解的结果；窗口再向右滑动，并继续寻找可行解，直到右

侧到达终点。 此题有改良思路，即先对搜索字符串中去掉不存在于目标字符串中的字符，这样滑动匹配次数就更少了。

我做了一个动图，解释找到第一个可行解 {ABEC}，既首次匹配到{A:1,B:1,C:1}的过程，注意此解不是最终解：

2 应用秒杀

既然明白了算法框架思路，来做秒杀，题1，力扣第 567 题Medium级别：

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。示例，输入: s1 = "ab"，

s2 = "eidbaooo"，输出: True，解释: s2 包含 s1 的排列之一 ("ba").

参考上面的算法，直接裁剪一下就出来了(Java)：

private static boolean subString(String s,String t){
    if (s.length()==0 || t.length() ==0){
        return false;
    }
    Map targetMap = new HashMap(8);
    for (int i = 0; i         // 目标串中可能有重复字符，
        int count = targetMap.getOrDefault(t.charAt(i),0);
        targetMap.put(t.charAt(i),count + 1);
    }
    Map winMap = new HashMap(16);
    int left = 0,right = 0 ;
    int match = 0;
    while(right         char c = s.charAt(right);
        int count = winMap.getOrDefault(c,0);
        winMap.put(c,count + 1);
        // 右侧一直向右滑动，直到包含了目标串的所有字符排列
        if (targetMap.containsKey(c) && targetMap.get(c).intValue() == winMap.get(c)){
            match ++;
        }
        right ++;
        // 窗口左侧向右滑动，判断满足所有字符排列的子串
        while (left             // 如果子串长度等于目标串长度，即为可行解
            if (right - left + 1 == targetMap.size()){
                return true;
            }
            c = s.charAt(left);
            if (targetMap.containsKey(c) && targetMap.get(c).intValue() == winMap.get(c)){
                count = winMap.getOrDefault(c,0);
                winMap.put(c,count -1);
                match --;
            }
            left ++;
        }
    }
    return false;
}

代码解析：在窗口扩大滑动过程中，先找到包含了目标串所有字符的子串，然后左侧滑动缩小，如果同时满足

窗口中子串长度和目标串长度一样，因为既包含了所有字符且长度一样的子串肯定为一个排列，即为可行解！

秒杀题2，力扣第3题 Medium级别：

给定一个字符串，请你输出其中不含有重复字符的最长子串。示例: 输入， "ABEBCDEE"， 输出："EBCD"，

我这里并非原题，做了个变形，要求输出子串，而不是给出个长度值，解法如下：

/**查找最长无重复子串*/
private static String subString(String s) {
    if (s.length()==0){
        return "";
    }
    int left = 0,right = 0;
    Map winMap = new HashMap(8);
    int[] position={0,0,0};
    while (right         char c = s.charAt(right);
        int count = winMap.getOrDefault(c,0);
        winMap.put(c, count + 1);
        if (right - left > position[0]){
            position[0]= right - left;
            position[1]= left;
            position[2]= right;
        }
        while (winMap.get(c) > 1){
            if (s.charAt(right) == s.charAt(left)){
                count = winMap.get(c);
                winMap.put(c,count - 1);
            }
            left ++;
        }
        right ++;
    }
    return s.substring(position[1],position[2]);
}

代码解析：如何找重复字符？即记录字符个数并累加，大于1的即存在重复。同样是滑动窗口，但注意使用一个

数组记录可行解，然后对比其他可行解，并只保留最优解。注意，最长无重复子串不唯一，如"ABEBCDEE"，

可行解为"EBCD"或者"BCDE"，故原题仅输出长度值而只有唯一解。另外，这里其实有个优化思路，每次窗口右

侧发现有重复字符，窗口左侧滑动时，可以不必逐字符滑动，可以直接定位到重复字符的下一位即可。

后记：总以为算法平时用的少，工作也不是算法岗，所以没必要去研究，可是遭到社会的毒打后，才知道算法是很重要的，共勉！

全文完！

我近期其他文章：

• 1 聊聊算法——回溯算法
• 2 Redis高级应用
• 3 聊聊算法——BFS和DFS
• 4 微服务通信方式——gRPC
• 5 分布式任务调度系统

只写原创，敬请关注 

聊聊算法——滑动窗口

标签：keyword   length   ima   abc   调度系统   ddc   red   instr   title   

原文地址：https://www.cnblogs.com/xxbiao/p/12968579.html