聊聊演算法——滑動窗口
有看到一句話，我深以為然：「所有演算法的終極數據結構只有兩種：數組和鏈表！」其他所有數據結構都是數組或鏈表的衍生品，
不管是樹還是圖或者棧，至於演算法就最終都落到了這兩種結構的操作上，滑動窗口也不例外！滑動窗口的應用場景還是很多的：
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”，故原題僅輸出長度值而只有唯一解。另外，這裡其實有個優化思路，每次窗口右
側發現有重複字元，窗口左側滑動時，可以不必逐字元滑動，可以直接定位到重複字元的下一位即可。
後記：總以為演算法平時用的少，工作也不是演算法崗，所以沒必要去研究，可是遭到社會的毒打後，才知道演算法是很重要的，共勉！
全文完！
我近期其他文章：
只寫原創，敬請關注
