聊聊算法——滑动窗口

数据与算法之美 2020-05-26

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

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

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

作者原创文章,谢绝一切转载,违者必究!

准备:

Idea2019.03/JDK11.0.4

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

目标:

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

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",故原题仅输出长度值而只有唯一解。另外,这里其实有个优化思路,每次窗口右

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

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

全文完!


我近期其他文章:

只写原创,敬请关注 

聊聊算法——滑动窗口

相关推荐