聊聊算法——滑动窗口

数据与算法之美

2020-05-26

关注关注

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

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

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

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

准备：

Idea2019.03/JDK11.0.4

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

目标：

滑动窗口算法分析与应用

1 算法框架

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

/* 滑动窗口算法框架 */private static void minWindow(String s,String t){    // 滑动窗口左右侧位置指针    int left = 0,right = 0;    while (right < s.length()){        // 滑动窗口右边增加        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<Character,Integer> dictT = new HashMap<>(8);        for (int i = 0; i < t.length(); 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<Character,Integer> winStrMap = new HashMap<>(16);        // 窗口内子串与目标串字符匹配的个数        int formed = 0;        // 记录最小窗口长度，{窗口长，left，right}        int[] ans = {-1,0,0};        //窗口进行滑动        while (right < s.length()){            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 < right && formed == required){                c = s.charAt(left);                //计算最小窗口长                if( ans[0] == -1 || (right - left + 1 < ans[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) < dictT.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<Character,Integer> targetMap = new HashMap<>(8);    for (int i = 0; i < t.length(); i++) {        // 目标串中可能有重复字符，        int count = targetMap.getOrDefault(t.charAt(i),0);        targetMap.put(t.charAt(i),count + 1);    }    Map<Character,Integer> winMap = new HashMap<>(16);    int left = 0,right = 0 ;    int match = 0;    while(right < s.length()){        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 < right && match == targetMap.size()){            // 如果子串长度等于目标串长度，即为可行解            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<Character,Integer> winMap = new HashMap<>(8);    int[] position={0,0,0};    while (right < s.length()){        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"，故原题仅输出长度值而只有唯一解。另外，这里其实有个优化思路，每次窗口右

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

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

全文完！

我近期其他文章：