聊聊算法——滑动窗口
甲由崽 人气:0有看到一句话，我深以为然：“所有算法的终极数据结构只有两种：数组和链表！”其他所有数据结构都是数组或链表的衍生品，
不管是树还是图或者栈，至于算法就最终都落到了这两种结构的操作上，滑动窗口也不例外！滑动窗口的应用场景还是很多的：
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"，故原题仅输出长度值而只有唯一解。另外，这里其实有个优化思路，每次窗口右
侧发现有重复字符，窗口左侧滑动时，可以不必逐字符滑动，可以直接定位到重复字符的下一位即可。
后记：总以为算法平时用的少，工作也不是算法岗，所以没必要去研究，可是遭到社会的毒打后，才知道算法是很重要的，共勉！
全文完！
我近期其他文章：
- 1 聊聊算法——回溯算法
- 2 Redis高级应用
- 3 聊聊算法——BFS和DFS
- 4 微服务通信方式——gRPC
- 5 分布式任务调度系统
只写原创，敬请关注
加载全部内容