滑动窗口算法通常用于字符串中查找满足条件的子串（所有子串或者最长或最短子串）。
滑动窗口算法的思路是这样：
1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个「窗口」。
2、我们先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的字符串符合要求。
3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求同时，每次增加 left，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。
第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，记录比较每一个优化过的可行解找到最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。
上述过程可以简单地写出如下伪码框架：
int left = 0, right = 0;
while(right < s.size()) {
window.add(s[right]);
right++;
// 如果符合要求，移动 left 缩小窗口
while (window 符合要求) {
更新结果。
window.remove(s[left]);
left++;
}
}
解决滑动窗口问题需要思考一下几个问题：
1、如何记录窗口的状态，也就是[left,right)时windows的状态
2、如何判断Windows符合要求
3、如何更新结果。
滑动窗口算法解决最小覆盖子串：
import java.util.HashMap;
import java.util.Map;
class Solution {
private int min_left=0;
private int min_right=Integer.MAX_VALUE;
private Map<Character,Integer> required=new HashMap<>();
public String minWindow(String s, String t) {
//将匹配串转换为map
for (char c : t.toCharArray()) {
required.compute(c, (k, v) -> {
if (v == null) {
return 1;
} else {
return v + 1;
}
});
}
Map<Character, Integer> map = new HashMap<>();
//match来记录覆盖了子串的多少类字符
int match=0;
int left=0,right=0;
//双指针解题模板
while (right<s.length()){
char c=s.charAt(right);
if(required.containsKey(c)){
map.compute(c, (k, v) -> {
if (v == null) {
return 1;
} else {
return v + 1;
}
});
if(map.get(c).equals(required.get(c))){
//某一类字符覆盖完毕
match++;
}
}
right++;
//所有类字符覆盖完毕
while (match==required.size()){
c=s.charAt(left);
map.computeIfPresent(c,(k,v)->v-1);
if(map.containsKey(c)&&map.get(c)<required.get(c)){
match--;
if(min_right-min_left>right-left){
min_right=right;
min_left=left;
}
}
left++;
}
}
if(min_right==Integer.MAX_VALUE){
return "";
}
return s.substring(min_left,min_right);
}
}
