什么是滑動(dòng)窗口（Sliding Window）
The Sliding Problem contains a sliding window which is a sub – list that runs over a Large Array which is an underlying collection of elements.
滑動(dòng)窗口算法可以用以解決數(shù)組/字符串的子元素問(wèn)題血淌，它可以將嵌套的循環(huán)問(wèn)題匕得，轉(zhuǎn)換為單循環(huán)問(wèn)題情连，降低時(shí)間復(fù)雜度只洒。
比如找最長(zhǎng)的全為1的子數(shù)組長(zhǎng)度〔瘴郏滑動(dòng)窗口一般從第一個(gè)元素開(kāi)始嵌溢，一直往右邊一個(gè)一個(gè)元素挪動(dòng)特碳。當(dāng)然了，根據(jù)題目要求增蹭，我們可能有固定窗口大小的情況滴某，也有窗口的大小變化的情況。
如何判斷使用滑動(dòng)窗口算法
如果題目中求的結(jié)果有以下情況時(shí)可使用滑動(dòng)窗口算法：
- 最小值 Minimum value
- 最大值 Maximum value
- 最長(zhǎng)值 Longest value
- 最短值 Shortest value
- K值 K-sized value
算法模板與思路
/* 滑動(dòng)窗口算法框架 */
void slidingWindow(string s, string t) {
unordered_map<char, int> need, window;
for (char c : t) need[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是將移入窗口的字符
char c = s[right];
// 右移窗口
right++;
// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
...
/*** debug 輸出的位置 ***/
printf("window: [%d, %d)\n", left, right);
/********************/
// 判斷左側(cè)窗口是否要收縮
while (window needs shrink) {
// d 是將移出窗口的字符
char d = s[left];
// 左移窗口
left++;
// 進(jìn)行窗口內(nèi)數(shù)據(jù)的一系列更新
...
}
}
}
滑動(dòng)窗口算法的思路：
- 在字符串 S 中使用雙指針中的左右指針技巧霎奢，初始化 left = right = 0 ，把索引左閉右開(kāi)區(qū)間 [left, right) 稱(chēng)為一個(gè)「窗口」饼灿。
- 不斷地增加 right 指針擴(kuò)大窗口 [left, right) 幕侠，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。
- 此時(shí)停止增加 right 碍彭，轉(zhuǎn)而不斷增加 left 指針縮小窗口 [left, right) 晤硕，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同時(shí)硕旗，每次增加 left 窗骑，都要更新一輪結(jié)果。
- 重復(fù)第2和第3步漆枚，直到 right 到達(dá)字符串 S 的盡頭创译。
needs 和 window 相當(dāng)于計(jì)數(shù)器，分別記錄 T 中字符出現(xiàn)次數(shù)和「窗口」中的相應(yīng)字符的出現(xiàn)次數(shù)墙基。
開(kāi)始套模板之前软族，要思考以下四個(gè)問(wèn)題：
- 當(dāng)移動(dòng) right 擴(kuò)大窗口刷喜，即加入字符時(shí)，應(yīng)該更新哪些數(shù)據(jù)立砸？
- 什么條件下掖疮，窗口應(yīng)該暫停擴(kuò)大，開(kāi)始移動(dòng)left 縮小窗口颗祝？
- 當(dāng)移動(dòng) left 縮小窗口浊闪，即移出字符時(shí)，應(yīng)該更新哪些數(shù)據(jù)螺戳？
- 我們要的結(jié)果應(yīng)該在擴(kuò)大窗口時(shí)還是縮小窗口時(shí)進(jìn)行更新搁宾？
滑動(dòng)窗口問(wèn)題實(shí)例
最小覆蓋子串
LeetCode題目：76.最小覆蓋子串
1、閱讀且分析題目
題目中包含關(guān)鍵字：時(shí)間復(fù)雜度O(n)倔幼、字符串盖腿、最小子串∷鹜可使用滑動(dòng)窗口算法解決翩腐。
2. 思考滑動(dòng)窗口算法四個(gè)問(wèn)題
1、當(dāng)移動(dòng) right 擴(kuò)大窗口膏燃，即加入字符時(shí)茂卦，應(yīng)該更新哪些數(shù)據(jù)？
更新 window 中加入字符的個(gè)數(shù)蹄梢，判斷 need 與 window 中的字符個(gè)數(shù)是否相等疙筹，相等則 valid++ 。
2禁炒、什么條件下而咆，窗口應(yīng)該暫停擴(kuò)大，開(kāi)始移動(dòng)left 縮小窗口幕袱？
當(dāng) window 包含 need 中的字符及個(gè)數(shù)時(shí)暴备，即 valid == len(need) 。
3们豌、當(dāng)移動(dòng) left 縮小窗口涯捻，即移出字符時(shí)，應(yīng)該更新哪些數(shù)據(jù)望迎？
更新 window 中移出字符的個(gè)數(shù)障癌，且判斷 need 與 window 中的移出字符個(gè)數(shù)是否相等，相等則 valid-- 辩尊。
4涛浙、我們要的結(jié)果應(yīng)該在擴(kuò)大窗口時(shí)還是縮小窗口時(shí)進(jìn)行更新？
在縮小窗口時(shí)，因?yàn)榍蟮氖亲钚∽哟?/p>
3. 代碼實(shí)現(xiàn)
func minWindow(s string, t string) string {
need, window := make(map[byte]int), make(map[byte]int)
for i := 0; i < len(t); i++ { // 初始化 need
if _, ok := need[t[i]]; ok {
need[t[i]]++
} else {
need[t[i]] = 1
}
}
left, right, valid := 0, 0, 0
start, slen := 0, len(s)+1 // 設(shè)置長(zhǎng)度為 len(s) + 1 表示此時(shí)沒(méi)有符合條件的子串
for right < len(s) { // 滑動(dòng)窗口向右擴(kuò)大
c := s[right]
right++
if _, ok := need[c]; ok { // 向右擴(kuò)大時(shí)轿亮，更新數(shù)據(jù)
if _, ok := window[c]; ok {
window[c]++
} else {
window[c] = 1
}
if window[c] == need[c] {
valid++
}
}
for valid == len(need) { // 當(dāng)窗口包括 need 中所有字符及個(gè)數(shù)時(shí)疮薇，縮小窗口
if right-left < slen { // 縮小前，判斷是否最小子串
start = left
slen = right - left
}
d := s[left]
left++
if v, ok := need[d]; ok { // 向左縮小時(shí)我注，更新數(shù)據(jù)
if window[d] == v {
valid--
}
window[d]--
}
}
}
if slen == len(s)+1 { // 長(zhǎng)度 len(s) + 1 表示此時(shí)沒(méi)有符合條件的子串
return ""
} else {
return s[start : start+slen]
}
}
4. 復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n)按咒，n 表示字符串 s 的長(zhǎng)度。遍歷一次字符串但骨。
- 空間復(fù)雜度：O(m)励七，m 表示字符串 t 的長(zhǎng)度。使用了兩個(gè)哈希表奔缠，保存字符串 t 中的字符個(gè)數(shù)呀伙。
字符串排列
LeetCode題目：567.字符串的排列
1、閱讀且分析題目
題目中包含關(guān)鍵字：字符串添坊、子串，且求 s2 中是否包含 s1 的排列箫锤，即求是否包含長(zhǎng)度 k 的子串贬蛙。可使用滑動(dòng)窗口算法解決谚攒。
2. 思考滑動(dòng)窗口算法四個(gè)問(wèn)題
1阳准、當(dāng)移動(dòng) right 擴(kuò)大窗口，即加入字符時(shí)馏臭，應(yīng)該更新哪些數(shù)據(jù)野蝇？
更新 window 中加入字符的個(gè)數(shù)，判斷 need 與 window 中的字符個(gè)數(shù)是否相等括儒，相等則 valid++ 绕沈。
2、什么條件下帮寻，窗口應(yīng)該暫停擴(kuò)大乍狐，開(kāi)始移動(dòng)left 縮小窗口？
當(dāng) window 包含 need 中的字符及個(gè)數(shù)時(shí)固逗，即 valid == len(need) 浅蚪。
3、當(dāng)移動(dòng) left 縮小窗口烫罩，即移出字符時(shí)惜傲，應(yīng)該更新哪些數(shù)據(jù)？
更新 window 中移出字符的個(gè)數(shù)贝攒，且判斷 need 與 window 中的移出字符個(gè)數(shù)是否相等盗誊，相等則 valid-- 。
4、我們要的結(jié)果應(yīng)該在擴(kuò)大窗口時(shí)還是縮小窗口時(shí)進(jìn)行更新浊伙？
無(wú)論在擴(kuò)大時(shí)或縮小窗口時(shí)都可以撞秋，因?yàn)榍蟮氖枪潭ㄩL(zhǎng)度的子串。選擇在縮小窗口時(shí)更新嚣鄙。
3. 代碼實(shí)現(xiàn)
func checkInclusion(s1 string, s2 string) bool {
if s1 == s2 {
return true
}
need, window := make(map[byte]int), make(map[byte]int)
for i := 0; i < len(s1); i++ {
if _, ok := need[s1[i]]; ok {
need[s1[i]]++
} else {
need[s1[i]] = 1
}
}
left, right := 0, 0
valid := 0
for right < len(s2) {
c := s2[right]
right++
if _, ok := need[c]; ok {
if _, ok := window[c]; ok {
window[c]++
} else {
window[c] = 1
}
if window[c] == need[c] {
valid++
}
}
for valid == len(need) {
if right-left == len(s1) {
return true
}
d := s2[left]
left++
if _, ok := need[d]; ok {
if _, ok := window[d]; ok {
if window[d] == need[d] {
valid--
}
window[d]--
}
}
}
}
return false
}
4. 復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n)吻贿，n 表示字符串 s2 的長(zhǎng)度。遍歷一次字符串哑子。
- 空間復(fù)雜度：O(m)舅列，m 表示字符串 s1 的長(zhǎng)度。使用了兩個(gè)哈希表卧蜓，保存字符串 s1 中的字符個(gè)數(shù)帐要。
找所有字母異位詞
LeetCode題目：438.找到字符串中所有字母異位詞
1、閱讀且分析題目
題目中包含關(guān)鍵字：字符串弥奸，且求 s 中的所有 p 的字母異位詞的子串榨惠。可使用滑動(dòng)窗口算法解決盛霎。
2. 思考滑動(dòng)窗口算法四個(gè)問(wèn)題
1赠橙、當(dāng)移動(dòng) right 擴(kuò)大窗口，即加入字符時(shí)愤炸，應(yīng)該更新哪些數(shù)據(jù)期揪？
更新 window 中加入字符的個(gè)數(shù)，判斷 need 與 window 中的字符個(gè)數(shù)是否相等规个，相等則 valid++ 凤薛。
2、什么條件下诞仓，窗口應(yīng)該暫停擴(kuò)大缤苫，開(kāi)始移動(dòng)left 縮小窗口？
當(dāng) window 包含 need 中的字符及個(gè)數(shù)時(shí)墅拭，即 valid == len(need) 榨馁。
3、當(dāng)移動(dòng) left 縮小窗口帜矾，即移出字符時(shí)翼虫，應(yīng)該更新哪些數(shù)據(jù)？
更新 window 中移出字符的個(gè)數(shù)屡萤，且判斷 need 與 window 中的移出字符個(gè)數(shù)是否相等珍剑，相等則 valid-- 。
4死陆、我們要的結(jié)果應(yīng)該在擴(kuò)大窗口時(shí)還是縮小窗口時(shí)進(jìn)行更新招拙？
無(wú)論在擴(kuò)大時(shí)或縮小窗口時(shí)都可以唧瘾，因?yàn)榍蟮氖枪潭ㄩL(zhǎng)度的子串。選擇在縮小窗口時(shí)更新别凤。
3. 代碼實(shí)現(xiàn)
func findAnagrams(s string, p string) []int {
need, window := make(map[byte]int), make(map[byte]int)
for i := 0; i < len(p); i++ { // 初始化
if _, ok := need[p[i]]; ok {
need[p[i]]++
} else {
need[p[i]] = 1
}
}
left, right := 0, 0
valid := 0
ans := make([]int, 0)
for right < len(s) {
c := s[right]
right++
if _, ok := need[c]; ok {
if _, ok := window[c]; ok {
window[c]++
} else {
window[c] = 1
}
if need[c] == window[c] {
valid++
}
}
for valid == len(need) {
if right-left == len(p) {
ans = append(ans, left)
}
d := s[left]
left++
if _, ok := need[d]; ok {
if _, ok := window[d]; ok {
if need[d] == window[d] {
valid--
}
window[d]--
}
}
}
}
return ans
}
4. 復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n)饰序，n 表示字符串 s 的長(zhǎng)度。遍歷一次字符串规哪。
- 空間復(fù)雜度：O(m)求豫，m 表示字符串 p 的長(zhǎng)度。使用了兩個(gè)哈希表诉稍，保存字符串 p 中的字符個(gè)數(shù)蝠嘉。
最長(zhǎng)無(wú)重復(fù)子串
LeetCode題目：3. 無(wú)重復(fù)字符的最長(zhǎng)子串
1、閱讀且分析題目
題目中包含關(guān)鍵字：時(shí)間復(fù)雜度O(n)杯巨、字符串蚤告、最小子串》可使用滑動(dòng)窗口算法解決杜恰。
2. 思考滑動(dòng)窗口算法四個(gè)問(wèn)題
1、當(dāng)移動(dòng) right 擴(kuò)大窗口仍源，即加入字符時(shí)箫章，應(yīng)該更新哪些數(shù)據(jù)？
更新 window 中加入字符的個(gè)數(shù)镜会，及當(dāng) window 中的某個(gè)字符個(gè)數(shù) == 2時(shí)，更新 valid == false 终抽。
2戳表、什么條件下，窗口應(yīng)該暫停擴(kuò)大昼伴，開(kāi)始移動(dòng)left 縮小窗口匾旭？
當(dāng) window 中的字符及個(gè)數(shù) == 2時(shí)，即 valid == false 圃郊。
3价涝、當(dāng)移動(dòng) left 縮小窗口，即移出字符時(shí)持舆，應(yīng)該更新哪些數(shù)據(jù)色瘩？
更新 window 中移出字符的個(gè)數(shù)，且判斷 window 中移出字符個(gè)數(shù)是否 == 2 逸寓，相等則 valid == true 居兆。
4、我們要的結(jié)果應(yīng)該在擴(kuò)大窗口時(shí)還是縮小窗口時(shí)進(jìn)行更新竹伸？
在擴(kuò)大窗口時(shí)泥栖，因?yàn)榍蟮氖亲畲笞哟?/p>
3. 代碼實(shí)現(xiàn)
func lengthOfLongestSubstring(s string) int {
if s == "" { // 當(dāng)字符串為空時(shí)，返回0
return 0
}
window := make(map[byte]int)
left, right, max := 0, 0, 0
valid := true
for right < len(s) {
c := s[right]
right++
if _, ok := window[c]; !ok { // 初始化
window[c] = 0
}
window[c]++ // 累加
if window[c] == 2 { // 當(dāng)出現(xiàn)重復(fù)字符時(shí)
valid = false
} else { // 否則累加不重復(fù)子串長(zhǎng)度，并且判斷是否當(dāng)前最長(zhǎng)
if max < right-left {
max = right - left
}
}
for valid == false {
d := s[left]
left++
if window[d] == 2 {
valid = true
}
window[d]--
}
}
return max
}
4. 復(fù)雜度分析
- 時(shí)間復(fù)雜度：O(n)吧享，n 表示字符串 s 的長(zhǎng)度魏割。遍歷一次字符串。
- 空間復(fù)雜度：O(n)钢颂，n 表示字符串 s 的長(zhǎng)度钞它。使用了哈希表，保存不重復(fù)的字符個(gè)數(shù)甸陌。
總結(jié)
- 滑動(dòng)窗口算法可以用以解決數(shù)組/字符串的子元素問(wèn)題须揣，它可以將嵌套的循環(huán)問(wèn)題，轉(zhuǎn)換為單循環(huán)問(wèn)題钱豁，降低時(shí)間復(fù)雜度耻卡。
- 問(wèn)題中包含字符串子元素、最大值牲尺、最小值卵酪、最長(zhǎng)、最短谤碳、K值等關(guān)鍵字時(shí)溃卡，可使用滑動(dòng)窗口算法。
- 模板中的向左和向右時(shí)的處理是對(duì)稱(chēng)的蜒简。
- 套模板前思考四個(gè)問(wèn)題：
- 當(dāng)移動(dòng) right 擴(kuò)大窗口瘸羡，即加入字符時(shí)，應(yīng)該更新哪些數(shù)據(jù)搓茬？
- 什么條件下犹赖，窗口應(yīng)該暫停擴(kuò)大，開(kāi)始移動(dòng)left 縮小窗口卷仑？
- 當(dāng)移動(dòng) left 縮小窗口峻村，即移出字符時(shí)，應(yīng)該更新哪些數(shù)據(jù)锡凝？
- 我們要的結(jié)果應(yīng)該在擴(kuò)大窗口時(shí)還是縮小窗口時(shí)進(jìn)行更新粘昨？
