什麼是「滑動窗口演算法」（sliding window algorithm），有哪些應用場景？

---

概念

滑動窗口演算法可以用以解決數組/字元串的子元素問題，它可以將嵌套的循環問題，轉換為單循環問題，降低時間複雜度。

示例1

給定一個整數數組，計算長度為 k 的連續子數組的最大總和。

輸入：arr [] = {100,200,300,400}
k = 2

輸出：700

解釋：300 + 400 = 700

暴力法

我們可以很容易想到暴力法來解決這個問題，使用兩個 for 循環來不斷查找長度為 k 的最大總和。

JavaScript 示例代碼

function maxSum(arr, k) {
const n = arr.length
let maxSum = Number.MIN_SAFE_INTEGER;

for (let i = 0; i &< n - k + 1; i++) { let currentSum = 0; for (let j = 0; j &< k; j++) { currentSum = currentSum + arr[i + j]; } maxSum = Math.max(currentSum, maxSum); } return maxSum; }

因為包含兩個 for 循環，它的時間複雜度是 O（k * n）。

滑動窗口演算法

滑動窗口演算法可以將嵌套的循環問題，轉換為單循環問題，降低時間複雜度。

根據示例，當 k 等於 2 時，我們維護一個長度為 2 的窗口。

• 窗口內的值的和保存在一個變數中；
• 通過不斷的往右滑動來算出當前窗口的值，並與保存的最大值作比較；
• 當窗口滑動到最右邊時終止滑動；

JavaScript 示例代碼

function maxSum(arr, k) {
const n = arr.length;
if (n &< k) { return -1; } // 計算出第一個窗口的值 let maxSum = 0; for (let i = 0; i &< k; i++) { maxSum += arr[i]; } let sum = maxSum; for (let i = k; i &< n; i++) { // 新窗口的和 = 前一個窗口的和 + 新進入窗口的值 - 移出窗口的值 sum += arr[i] - arr[i - k]; maxSum = Math.max(maxSum, sum); } return maxSum; }

我們在一個循環中計算出了長度為 k 的子數組的最大總和，它的時間複雜度是 O（n）。我們可以使用滑動窗口演算法解決 查找最大/最小k子陣列，XOR，乘積，求和等問題。

示例2

給定一個字元串 S 和一個字元串 T，請在 S 中找出包含 T 所有字母的最小子串。(minimum-window-substring)

輸入: S = "ADOBECODEBANC", T = "ABC"
輸出: "BANC"

這個問題讓我們無法按照示例 1 中的方法進行查找，因為它不是給定了窗口大小讓你找對應的值，而是給定了對應的值，讓你找最小的窗口。

我們仍然可以使用滑動窗口演算法，只不過需要換一個思路。

既然是找最小的窗口，我們先定義一個最小的窗口，也就是長度為 0 的窗口。

我們比較一下當前窗口在的位置的字母，是否是 T 中的一個字母。

很明顯， A 是 ABC 中的一個字母，也就是 T 所有字母的最小子串 可能包含當前位置的 S 的值。

如果包含，我們開始擴大窗口，直到擴大後的窗口能夠包含 T 所有字母。

假設題目是 在 S 中找出包含 T 所有字母的第一個子串，我們就已經解決問題了，但是題目是找到最小的子串，就會存在一些問題。

• 當前窗口內可能包含了一個更小的能滿足題目的窗口
• 窗口沒有滑動到的位置有可能包含了一個更小的能滿足題目的窗口

為了解決可能出現的問題，當我們找到第一個滿足的窗口後，就從左開始縮小窗口。

• 如果縮小後的窗口仍滿足包含 T 所有字母的要求，則當前窗口可能是最小能滿足題目的窗口，儲存下來之後，繼續從左開始縮小窗口。
• 如果縮小後的窗口不能滿足包含 T 所有字母的要求，則縮小窗口停止，從右邊開始擴大窗口。

不斷重複上面的步驟，直到窗口滑動到最右邊，且找不到合適的窗口為止。最小滿足的窗口就是我們要找的 S 中包含 T 所有字母的最小子串。

JavaScript 示例代碼

/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
const map = {};
for (let i = 0; i &< t.length; i++) { if (map[t[i]]) { map[t[i]]++; } else { map[t[i]] = 1; } } let left = 0; let right = 0; let count = t.length; let max = Number.MAX_SAFE_INTEGER; let res = s; while (right &< s.length) { if (map[s[right]] &> 0) {
count--;
}
map[s[right]]--;
right++;

while (count === 0) {
if (right - left &< max) { max = right - left; res = s.slice(left, right); } map[s[left]]++; if (map[s[left]] &> 0) {
count++;
}
left++;
}
}
return max === Number.MAX_SAFE_INTEGER ? "" : res;
};


它的時間複雜度是 O（s + t）

示例3

給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。(longest-substring-without-repeating-characters)

輸入: "abcabcbb"
輸出: 3
解釋: 因為無重複字元的最長子串是 "abc"，所以其長度為 3。

和示例 2 相似，我們不斷的擴大/縮小窗口，把無重複字母的窗口大小保存下來，直到窗口滑動結束，就找到了不含有重複字元的 最長子串 的長度。

JavaScript 示例代碼

/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
const map = {};

let left = 0;
let right = 0;

let max = 0;
while (right &< s.length) { if (!map[s[right]]) { map[s[right]] = 1; right++; } else { while (left &< right) { delete map[s[left]]; if (map[s[left++]] === map[s[right]]) { break; } } } max = Math.max(max, right - left); } return max; };

時間複雜度是 O（n）

示例4

給定一個字元串 s 和一個非空字元串 p，找到 s 中所有是 p 的字母異位詞的子串，返回這些子串的起始索引。(find-all-anagrams-in-a-string)

輸入:
s: "cbaebabacd" p: "abc"

輸出:
[0, 6]

解釋:
起始索引等於 0 的子串是 "cba", 它是 "abc" 的字母異位詞。
起始索引等於 6 的子串是 "bac", 它是 "abc" 的字母異位詞。

與示例 1 類似，我們維護一個長度為 p 的窗口，然後不斷往右滑動查找當前窗口是否為 p 的字母異位詞。

var findAnagrams = function(s, p) {
const map = new Array(26).fill(0);

for (let i = 0; i &< p.length; i++) { map[p[i].charCodeAt() - 97]++; } const r = []; for (let i = 0, j = 0; i &< s.length; i++) { const c = s[i].charCodeAt() - 97; map[c]--; while (map[c] &< 0) { const c2 = s[j].charCodeAt() - 97; j++; map[c2]++; } if (i - j + 1 === p.length) { r.push(j); } } return r; };

時間複雜度為 O（s + p）

滑動窗口演算法的應用

TCP 流量控制

參考：

Window Sliding Technique - GeeksforGeeks

https://www.youtube.com/watch?v=eS6PZLjoaq8t=548s

sliding window algorithm

---

前言科普：什麼是滑動窗口演算法

滑動問題包含一個滑動窗口，它是一個運行在一個大數組上的子列表，該數組是一個底層元素集合。

假設有數組 [a b c d e f g h ]，一個大小為 3 的 滑動窗口 在其上滑動，則有：

[a b c]
[b c d]
[c d e]
[d e f]
[e f g]
[f g h]

一般情況下就是使用這個窗口在數組的 合法區間 內進行滑動，同時 動態地 記錄一些有用的數據，很多情況下，能夠極大地提高演算法地效率。

1. 滑動窗口最大值

題目來源於 LeetCode 上第 239 號問題：滑動窗口最大值。題目難度為 Hard，目前通過率為 40.5% 。

題目描述

給定一個數組 nums，有一個大小為 k 的滑動窗口從數組的最左側移動到數組的最右側。你只可以看到在滑動窗口 k 內的數字。滑動窗口每次只向右移動一位。

返回滑動窗口最大值。

示例:

輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7]
解釋:
?
滑動窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

題目解析

利用一個 雙端隊列，在隊列中存儲元素在數組中的位置， 並且維持隊列的嚴格遞減,，也就說維持隊首元素是 最大的 ，當遍歷到一個新元素時, 如果隊列里有比當前元素小的，就將其移除隊列，以保證隊列的遞減。當隊列元素位置之差大於 k，就將隊首元素移除。

補充：什麼是雙端隊列（Dqueue）

Deque 的含義是 「double ended queue」，即雙端隊列，它具有隊列和棧的性質的數據結構。顧名思義，它是一種前端與後端都支持插入和刪除操作的隊列。

Deque 繼承自 Queue（隊列），它的直接實現有 ArrayDeque、LinkedList 等。

動畫描述

代碼實現

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
//有點坑，題目里都說了數組不為空，且 k &> 0。但是看了一下，測試用例裡面還是有nums = [], k = 0，所以只好加上這個判斷
if (nums == null || nums.length &< k || k == 0) return new int[0]; int[] res = new int[nums.length - k + 1]; //雙端隊列 Deque& deque = new LinkedList&<&>();
for (int i = 0; i &< nums.length; i++) { //在尾部添加元素，並保證左邊元素都比尾部大 while (!deque.isEmpty() nums[deque.getLast()] &< nums[i]) { deque.removeLast(); } deque.addLast(i); //在頭部移除元素 if (deque.getFirst() == i - k) { deque.removeFirst(); } //輸出結果 if (i &>= k - 1) {
res[i - k + 1] = nums[deque.getFirst()];
}
}
return res;
}
}

2. 無重複字元的最長子串

題目來源於 LeetCode 上第 3 號問題：無重複字元的最長子串。題目難度為 Medium，目前通過率為 29.0% 。

題目描述

給定一個字元串，請你找出其中不含有重複字元的 最長子串 的長度。

示例 1:

輸入: "abcabcbb"
輸出: 3
解釋: 因為無重複字元的最長子串是 "abc"，所以其長度為 3。

題目解析

建立一個256位大小的整型數組 freg ，用來建立字元和其出現位置之間的映射。

維護一個滑動窗口，窗口內的都是沒有重複的字元，去儘可能的擴大窗口的大小，窗口不停的向右滑動。

• （1）如果當前遍歷到的字元從未出現過，那麼直接擴大右邊界；
• （2）如果當前遍歷到的字元出現過，則縮小窗口（左邊索引向右移動），然後繼續觀察當前遍歷到的字元；
• （3）重複（1）（2），直到左邊索引無法再移動；
• （4）維護一個結果res，每次用出現過的窗口大小來更新結果 res，最後返回 res 獲取結果。

動畫描述

代碼實現

// 滑動窗口
// 時間複雜度: O(len(s))
// 空間複雜度: O(len(charset))
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int freq[256] = {0};
int l = 0, r = -1; //滑動窗口為s[l...r]
int res = 0;
// 整個循環從 l == 0; r == -1 這個空窗口開始
// 到l == s.size(); r == s.size()-1 這個空窗口截止
// 在每次循環里逐漸改變窗口, 維護freq, 並記錄當前窗口中是否找到了一個新的最優值
while(l &< s.size()){ if(r + 1 &< s.size() freq[s[r+1]] == 0){ r++; freq[s[r]]++; }else { //r已經到頭 || freq[s[r+1]] == 1 freq[s[l]]--; l++; } res = max(res, r-l+1); } return res; } };

3. 存在重複元素 II

題目來源於 LeetCode 上第 219 號問題：存在重複元素 II。題目難度為 Easy，目前通過率為 33.9% 。

題目描述

給定一個整數數組和一個整數 k，判斷數組中是否存在兩個不同的索引 i 和 j，使得 nums [i] = nums [j]，並且 i 和 j 的差的絕對值最大為 k。

題目解析

使用用滑動窗口與查找表來解決。

• 設置查找表record，用來保存每次遍歷時插入的元素，record的最大長度為k
• 遍曆數組nums，每次遍歷的時候在record查找是否存在相同的元素，如果存在則返回true，遍歷結束
• 如果此次遍歷在record未查找到，則將該元素插入到record中，而後查看record的長度是否為k + 1
• 如果此時record的長度是否為k + 1，則刪減record的元素，該元素的值為nums[i - k]
• 如果遍歷完整個數組nums未查找到則返回false
  動畫描述

代碼實現

// 時間複雜度: O(n)

// 空間複雜度: O(k)

class Solution {

public:

bool containsNearbyDuplicate(vector& nums, int k) {

if(nums.size() &<= 1) return false;

if(k &<= 0) return false;

unordered_set& record;

for(int i = 0 ; i &< nums.size() ; i ++){

if(record.find(nums[i]) != record.end()){

return true;

}

record.insert(nums[i]);

// 保持record中最多有k個元素

// 因為在下一次循環中會添加一個新元素,使得總共考慮k+1個元素

if(record.size() == k + 1){

record.erase(nums[i - k]);

}

}

return false;

}

};

4. 長度最小的子數組

題目來源於 LeetCode 上第 209 號問題：長度最小的子數組。題目難度為 Medium，目前通過率為 37.7% 。

題目描述

給定一個含有 n 個正整數的數組和一個正整數 s ，找出該數組中滿足其和 ≥ s 的長度最小的連續子數組。如果不存在符合條件的連續子數組，返回 0。

示例:

輸入: s = 7, nums = [2,3,1,2,4,3]
輸出: 2
解釋: 子數組 [4,3] 是該條件下的長度最小的連續子數組。
// 滑動窗口的思路
// 時間複雜度: O(n)
// 空間複雜度: O(1)
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int l= 0,r = -1; // nums[l...r]為我們的滑動窗口
int sum = 0;
int result = nums.length + 1;
while (l &< nums.length){ // 窗口的左邊界在數組範圍內,則循環繼續 ? if( r+1 &= s
sum -= nums[l];
l++;
}
?
if(sum &>= s){
result = (r-l+1) &< result ? (r-l+1) : result ; } } if(result==nums.length+1){ return 0; } return result; } }

4. 長度最小的子數組

題目來源於 LeetCode 上第 209 號問題：長度最小的子數組。題目難度為 Medium，目前通過率為 37.7% 。

題目描述

給定一個含有 n 個正整數的數組和一個正整數 s ，找出該數組中滿足其和 ≥ s 的長度最小的連續子數組。如果不存在符合條件的連續子數組，返回 0。

示例:

輸入: s = 7, nums = [2,3,1,2,4,3]
輸出: 2
解釋: 子數組 [4,3] 是該條件下的長度最小的連續子數組。


題目解析

定義兩個指針 left 和 right ，分別記錄子數組的左右的邊界位置。

• （1）讓 right 向右移，直到子數組和大於等於給定值或者 right 達到數組末尾；
• （2）更新最短距離，將 left 像右移一位, sum 減去移去的值；
• （3）重複（1）（2）步驟，直到 right 到達末尾，且 left 到達臨界位置

動畫描述

設置滑動窗口的長度為 0 ，位於數軸的最左端。

1 .滑動窗口右端 R 開始移動，直到區間滿足給定的條件，也就是和大於 7 ，此時停止於第三個元素 2，當前的最優長度為 4

2. 滑動窗口左端 L 開始移動，縮小滑動窗口的大小，停止於第一個元素 3，此時區間和為 6，使得區間和不滿足給定的條件（此時不大於 7）

3. 滑動窗口右端 R 繼續移動，停止於第四個元素 4，此時和位 10 ，但最優長度仍然為 4

代碼實現

// 滑動窗口的思路
// 時間複雜度: O(n)
// 空間複雜度: O(1)
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int l= 0,r = -1; // nums[l...r]為我們的滑動窗口
int sum = 0;
int result = nums.length + 1;
while (l &< nums.length){ // 窗口的左邊界在數組範圍內,則循環繼續 ? if( r+1 &= s
sum -= nums[l];
l++;
}
?
if(sum &>= s){
result = (r-l+1) &< result ? (r-l+1) : result ; } } if(result==nums.length+1){ return 0; } return result; } }

我的專欄：

和程序員小吳一起學演算法?

zhuanlan.zhihu.com

?? 看完三件事：

如果你覺得這篇內容對你挺有啟發，我想邀請你幫我三個忙：

1. 點贊，讓更多的人也能看到這篇內容（收藏不點贊，都是耍流氓 -_-）
2. 關注我和專欄，讓我們成為長期關係
3. 關注公眾號「五分鐘學演算法」，第一時間閱讀最新的演算法文章，公眾號後台回復 1024 送你 50 本 演算法編程書籍。

---

計算機網路中的滑動窗口請參閱相關書籍。

滑動窗口本質上來源於單調性，一般可以理解為，隨著左端點位置的增加，其最優決策的右端點位置單調不減。

事實上是利用決策單調性來實現複雜度優化。

具體例題可以參見 @王天笑 回答中的第二三四題。

---

流量控制

比如TCP協議中

還有就是為服務的限流，滑動窗口演算法功能上相當於令牌桶演算法

---

STFT

---

編譯器中窺孔優化。

---

推薦閱讀：