【c++算法篇】滑動窗口

Alt

🔥個人主頁：Quitecoder

🔥專欄：算法筆記倉

Alt

滑動窗口是一種常用的算法技術，它適用于需要檢查序列（如數組或字符串）中的一系列連續元素的問題。通過維護序列中的一段特定大小的連續元素集，滑動窗口減少了不必要的重復計算，從而優化了性能。這種技術經常用于求解最大或者最小總和、長度滿足特定條件的子串或子數組的問題。

操作滑動窗口通常涉及以下幾個步驟：

初始化兩個指針，通常稱為 left 和 right，指向序列的起始部分，這定義了窗口的邊界。
根據問題的需要，將 right 指針向右移動以擴大窗口，直到窗口中的元素滿足特定條件（例如，元素總和達到目標值）。
當窗口中的元素滿足特定條件之后，可能需要將 left 指針向右移動以縮小窗口，并再次檢查條件是否滿足。在移動 left 指針的同時，我們可以更新相關的計算結果，如累積和或計數器等
在整個過程中，我們通常會記錄窗口相關的一些信息，如窗口大小、窗口內元素的總和、窗口中的最大或最小元素等，可能還會記錄與問題計算要求相關的最優結果
持續這個過程，有序地移動 left 和 right 指針，直到滑動窗口窮盡了整個序列的所有可能的連續元素集

一個常見的滑動窗口問題示例是找出一個數組中和至少為 target 的最短連續子數組，在這樣的問題中，滑動窗口技術能夠有效地找到解決方法，同時保證時間復雜度最少。

`1.長度最小的子數組`

題目鏈接：209. 長度最小的子數組
題目描述：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int right =0,left=0,len=INT_MAX;int sum=0;while(right<nums.size()){sum+=nums[right];while(sum>=target){len=min(len,right-left+1);sum-=nums[left++];}right++;}return len==INT_MAX?0:len;}
};

這段代碼解決的問題是尋找數組 nums 中和至少為 target 的最短連續子數組的長度。使用了滑動窗口方法，以下是它的邏輯和思路：

初始化兩個指針 left 和 right, 以及 sum 來存儲當前窗口中的元素和，和 len 來存儲最短子數組的長度。這里，len 初始化為 INT_MAX，表示一個非常大的數，用來保證能找到比初始值小的最小長度
使用外層 while 循環遍歷數組，右指針 right 逐漸向右移動，遍歷數組的每個元素。
在每次迭代中，把 right 指向的當前元素加到 sum 中。這擴大了當前的滑動窗口，包括了 right 指向的新元素
出現滑動窗口中的和大于等于 target 時，進入內層 while 循環。在內層循環中：

a. 通過 min(len, right-left+1) 更新 len 的值，以保持記錄最短連續子數組的長度。

b. 嘗試縮小窗口從而找到可能的更短的連續子數組，方法是減去滑動窗口左端的元素值 nums[left]，然后將左指針向右移動一位 (left++)
繼續執行外層 while 循環，右指針向右移動 (right++)。每次增加 right 時，重復上述過程，更新窗口中的元素和 sum，然后再次檢查窗口的和是否大于等于 target
當外層 while 循環結束時（即遍歷了所有元素），檢查最短長度 len 是否被更新過：如果 len 還是 INT_MAX，這意味著沒有找到滿足條件的子數組，函數返回 0；否則，返回找到的最短連續子數組的長度

這個時間復雜度是 O(n)，因為每個元素最多被訪問兩次：一次是右指針向右移動時，另一次是左指針向右移動時

`2.無重復字符的最長子串`

題目鏈接：3. 無重復字符的最長子串
題目描述：

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128]={0};int left=0,right=0,len=0;while(right<s.size()){hash[s[right]]++;while(hash[s[right]]>1) hash[s[left++]]--;len=max(len,right-left+1);right++;}return  len;}
};

尋找給定字符串 s 中最長不含重復字符的子串的長度。使用滑動窗口，并在窗口內部跟蹤了字符的出現情況。具體思路：

hash 數組用來維護每個 ASCII 字符在當前考慮的子串（滑動窗口）中的出現次數。它被初始化為0。
left 和 right 兩個指針用來表示滑動窗口的邊界，初始時都指向字符串的開頭
len 用來保持找到的最長不重復字符子串的長度
外層 while 循環用于移動 right 指針，這擴大了當前考慮的窗口
每次迭代中，在 hash 數組中增加 right 指向字符的計數
內層 while 循環檢查通過 right 新加入的字符是否導致了重復字符出現。如果是這樣，循環就使用 left 指針向前移動直到這個字符的計數再一次變為1
窗口內的字符統計更新后，計算當前窗口的長度并與之前的 len 比較，取較大者作為新的 len
right 指針向前移動一位，以便包含當前右邊界的下一個字符。
外層循環直到 right 到達字符串的末尾結束，這時所有可能的窗口都已經被考慮。
最終 len 就是最長不重復字符子串的長度。

代碼結束時返回的 len 是所求的最長子串長度

`3.最大連續1的個數 III`

題目鏈接：1004. 最大連續1的個數 III
題目描述：

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left=0,right=0,len=0,zero=0;while(right<nums.size()){if(nums[right]==0)zero++;while(k<zero){if(nums[left]==0) zero--,left++;else left++;}len=max(len,right-left+1);right++;}return len;  }
};

同樣的思路，用zero來記錄零的個數，如果zero大于二，移動左指針指導等于二位置，繼續將right向右移動，最后返回len的最大值

`4.將 x 減到 0 的最小操作數`

題目鏈接：1658.將 x 減到 0 的最小操作數
題目描述：

正難則反：

本題可以轉換為，求中間最長連續數組的和為數組總和減去x的結果

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum=0;for(int e:nums){sum+=e;}int des=sum-x;if(des<0)return -1;int left=0,right=0,len=-1,add=0;while(right<nums.size()){add+=nums[right];while(add>des){add-=nums[left++];}if(add==des){len=max(len,right-left+1);}right++;}return len==-1?-1:nums.size()-len;}
};

des是中間連續數組的目標求和值，add記錄連續子數組的和，如果和大于目標值，則讓add減去左指針指向的值并讓左指針移動，如果等于則記錄最大值，這里初始值給-1，如果沒有匹配的數組，則返回-1

`5.水果成籃`

題目鏈接：904.水果成籃
題目描述：

class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001]={0};int left=0,right=0,len=0,kinds=0;while(right<fruits.size()){if(hash[fruits[right]]==0) kinds++;hash[fruits[right]]++;while(kinds>2){hash[fruits[left]]--;if(hash[fruits[left]]==0)kinds--;left++;}len=max(len,right-left+1);right++;}return len;}
};

在給定一個整數數組 fruits 的情況下，找到最長的連續子數組（窗口），其中只包含最多兩種不同的元素（即果樹種類）。這個問題可以用滑動窗口算法解決：

hash 數組用來計數每種水果當前在窗口中的數量。
兩個變量 left 和 right 表示當前窗口（子數組）的兩端位置。
len 用來記錄窗口的最大長度。
kinds 用來記錄當前窗口中有多少種不同的水果

代碼的逐步邏輯：

外部 while 循環通過移動 right 指針向右擴展窗口，這樣就能包含新的元素（水果種類）。
如果當前 right 指針指向的水果種類之前未包含在窗口中（即 hash[fruits[right]] == 0），則增加 kinds 變量。
然后增加該水果種類的計數（hash[fruits[right]]++）。
內部 while 循環檢查 kinds 是否超過了2。如果是這樣，這表示當前窗口包含了超過兩種水果，不符合題目條件。在這種情況下，需要縮小窗口（移動 left 指針）直到窗口中只包含兩種水果。
if(hash[fruits[left]] == 0)這句代碼檢查減去左指針后是否已經不包含這種水果，如果不包含，則種類數 kinds 需要減少
此次循環結束后，更新窗口長度的最大值 len（max(len, right - left + 1)）。
當所有元素都被擴展到窗口中后，right 指針繼續向右移動，讓外部循環繼續執行。
當循環結束時，len 中存儲的就是滿足條件的最大窗口長度。

`6.找到字符串中所有字母異位詞`

題目鏈接：438.找到字符串中所有字母異位詞
題目描述：

因為字符串 p 的異位詞的長度?定與字符串 p 的?度相同，所以我們可以在字符串 s 中構
造?個長度為與字符串 p 的長度相同的滑動窗?，并在滑動中維護窗?中每種字?的數量；
當窗口中每種字母的數量與字符串 p 中每種字?的數量相同時，則說明當前窗口為字符串 p
的異位詞；
因此可以用兩個大小為 26 的數組來模擬哈希表，?個來保存 s 中的子串每個字符出現的個
數，另?個來保存 p 中每?個字符出現的個數。這樣就能判斷兩個串是否是異位詞

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> result;  if (s.length() < p.length()) {return result;}int left = 0, right = 0, n = p.size(), count = 0;int hash1[26] = {0};int hash2[26] = {0};for (char e : p) {hash1[e - 'a']++;}while (right < s.length()) {hash2[s[right] - 'a']++;if (hash2[s[right] - 'a'] <= hash1[s[right] - 'a']) {count++;}if (right - left + 1 > n) {if (hash2[s[left] - 'a'] <= hash1[s[left] - 'a']) {count--;}hash2[s[left] - 'a']--;left++;}if (count == n) {result.push_back(left);}right++;}return result;}
};

：

首先檢查 s 的長度是否小于 p 的長度，如果小于，則直接返回空結果集，因為 p 的異位詞長度必定與 p 相等
定義并初始化兩個長度為 26 的數組 hash1 和 hash2，這兩個哈希表用于存儲字符 ‘a’ 到 ‘z’ 在字符串 p 和當前檢查的 s 的子串中出現的次數
遍歷字符串 p 并更新 hash1 表，其中 hash1[e - 'a']++ 表示將字符 e 在 hash1 中的計數增加 1，用于記錄 p 里每個字符的頻率
使用兩個指針 left 和 right 定義滑動窗口的邊界。left 是窗口的起始位置，right 是窗口的結束位置，初始化時它們都是 0。變量 n 存儲字符串 p 的長度，count 用于記錄當前滑動窗口內字符頻率匹配 p 中的字符頻率的數量（即異位詞的字符計數）
開始遍歷字符串 s，同時動態更新 hash2 表，并增加 count 計數，表達式 hash2[s[right] - 'a']++ 用于更新 s 中當前字符的頻率
如果當前字符在 hash2 里的計數小于或等于 hash1 中的對應計數，count 增加 1，這意味著這個字符是 p 中的字符，并且在目前窗口中的出現頻率尚未超過 p 中的頻率
當滑動窗口的長度超過字符串 p 的長度時，必須移動窗口的左邊界。如果要移出窗口的字符的頻率在 hash2 中小于或等于 hash1，則減少 count 計數，并將 hash2[s[left] - 'a'] 減少 1，表示該字符從窗口中移除。
如果 count 與 p 的長度相等，這意味著當前窗口是 p 的一個異位詞，將當前窗口的起始索引 left 添加到結果集中。
移動窗口的右邊界以檢查下一個字符。
當遍歷完成時，返回包含所有異位詞起始索引的 result

與前面不同的是，這道題的窗口大小可以看做是固定的，left每次向右移動保證了窗口大小

`7.串聯所有單詞的子串`

題目鏈接：30.串聯所有單詞的子串
題目描述：

代碼思路：與上一道題類似，我們把每個words里面的元素當成一個整體，然后對s進行整體的劃分即可

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;if(s.empty() || words.empty() || words[0].size() > s.size())return ret;unordered_map<string, int> hash1; // 保存 words 里面所有單詞的頻次for(auto& word : words) hash1[word]++;int len = words[0].size(), m = words.size();int i = 0;while(i < len) { // 執行 len 次unordered_map<string, int> hash2; // 維護窗口內單詞的頻次int left = i, right = i, count = 0;while(right + len <= s.size()) {// 進窗口 + 維護 countstring in = s.substr(right, len);if(hash1.count(in)) {hash2[in]++;if(hash2[in] <= hash1[in]) count++;}// 判斷if(right - left + 1 > len * m) {// 出窗口 + 維護 countstring out = s.substr(left, len);if(hash1.count(out) && hash2[out] > 0) {if(hash2[out] <= hash1[out]) count--;hash2[out]--;}left += len;}// 更新結果if(count == m) ret.push_back(left);right += len; // 窗口右端向右移動}i++; // 處理下一個子串開始位置}return ret;}
};

繼續構建兩個哈希表

“執行 len 次”是指，對滑動窗口處理的起始點進行遍歷，而遍歷的次數等于單詞的長度 len。每個單詞長度相同，這個長度用 len 變量表示

`8.最小覆蓋子串`

題目鏈接：76.最小覆蓋子串
題目描述：

class Solution {
public:string minWindow(string s, string t) {string s1;if(s.size()<t.size())return s1;int hash1[128]={0};int hash2[128]={0};int kinds=0;int count=0;int len=INT_MAX;for(auto e:t){if(hash1[e]++ == 0) kinds++;}int left=0,right=0;int start=0;while(right<s.size()){hash2[s[right]]++;if(hash2[s[right]]==hash1[s[right]])count++;while(count==kinds){if(right - left + 1 < len) { len = right - left + 1;start = left; }hash2[s[left]]--;if(hash2[s[left]]<hash1[s[left]])count--;left++;}right++;}return len==INT_MAX?"":s.substr(start,len);}
};

思路：

預處理：
- 首先，檢查 s 的長度是否小于 t 的長度。若是，則無法包含所有 t 中的字符，直接返回空字符串。
- 初始化兩個哈希數組 hash1 和 hash2 來分別記錄 t 中每個字符的頻率和當前窗口中每個字符的頻率。數組大小設置為 128，以便覆蓋所有 ASCII 字符。
記錄 t 中字符的頻率：
- 遍歷字符串 t，并使用 hash1 統計每個字符出現的頻率。
- 如果字符 e 在 hash1 中的頻率從 0 變為 1，意味著 t 中又有一個新的字符，因此將 kinds 計數加 1，kinds 表示 t 中不同字符的種類數。
初始化變量：
- 初始化計數器 count 為 0，用于記錄當前窗口已滿足的 t 中不同字符的數量。
- 初始化 len 為 INT_MAX，用于記錄目前找到的最小窗口的長度。
- 初始化指針 left 和 right 為 0，它們表示滑動窗口的左右邊界。
移動右指針 right：
- 使用 while 循環，移動右指針 right 來拓展當前窗口，直到涵蓋了 t 中的所有字符。
- 增加 hash2[s[right]] 的值，表示當前字符在窗口中的計數增加。
- 如果 s[right] 在 hash2 中的計數與 hash1 中的計數相等，意味著至少包含了 t 中對應字符所要求的數量，count 加 1。
檢查并收縮窗口：
- 當 count 與 kinds 相等時，意味著當前窗口覆蓋了 t 中所有的字符。
- 進入另一個 while 循環，盡可能縮小窗口大小，移動左指針 left，同時更新 len 和 start 來記錄最小覆蓋子串的位置和長度。
- 在移動 left 指針之后，將 hash2[s[left]] 相應的值減少。如果減少后 hash2[s[left]] 的值小于了 hash1[s[left]]，意味著不能再移動 left 指針，因為移除的字符是 t 中必須有的字符，所以窗口不再滿足條件，需停止收縮。
移動右指針直到末尾：
- 繼續移動右指針 right，尋找下一個滿足條件的窗口。
返回結果：
- 當右指針遍歷完 s 后，檢查記錄的 len 是否變化，如果為 INT_MAX，表示沒有找到合適的窗口，返回空字符串。
- 如果 len 不為 INT_MAX，意味著找到了最小窗口子串，通過 s.substr(start, len) 獲取該子串并返回。