雙指針的特殊應用：滑動窗口

代碼

題目鏈接：https://leetcode.cn/problems/minimum-window-substring/description/
不說廢話，直接貼代碼：

static string minWindow(string s, string t) {// need記錄需要匹配的字符串t中每個字符及出現的次數// window記錄s中維護的窗口中對應need字符出現的次數（記錄其他字符沒有用）unordered_map<char, int> need, window;for (char c: t) {need[c]++;}int left = 0, right = 0;// valid記錄window中已經滿足（個數）要求的字符個數，如果一個字符在window中出現的次數等于need，那么該值加1int valid = 0;// 記錄最小覆蓋字串的起始索引及長度int start = 0, len = INT32_MAX;while (right < s.size()) {// 把right位置的元素移入窗口，并擴大窗口char c = s[right];right++;// 如果當前新增的字符屬于需要的字符，對window的記錄進行更新if (need.count(c)) {window[c]++;// 如果更新后該字符的個數已經達到need要求，進行記錄if (window[c] == need[c]) {valid++;}}// 如果當前window中所有字符的個數都滿足了need要求，說明左窗口可以收縮，以尋找更短的符合長度while (valid == need.size()) {// 如果當前新的符合條件的window長度小于之前記錄的長度，就更新記錄if (right - left < len) {start = left;len = right - left;}char d = s[left];// 縮小窗口left++;if (need.count(d)) {if (window[d] == need[d]) {valid--;}window[d]--;}}}return len == INT32_MAX ? "" : s.substr(start, len);
}

解題框架

關鍵點：

對于滑動窗口window

• 1.每次移入元素，都要考察
  （1）該元素是否是need中的
  （2）如果是，增加后它的個數是否滿足了need的要求
  如果所有元素的個數都滿足了need要求，說明可以收縮左邊界，以尋求更短的符合長度。
• 2.每次移出元素，都要考察
  （1）該元素是否是need中的
  （2）如果是，減少后它的個數是否就不滿足need要求了
  2.1 如果移出元素后，窗口所有元素的個數不滿足need要求了，說明不需要收縮左邊界了，需要繼續向右擴張邊界以尋找新的元素用來滿足need要求。
  2.2 如果移出元素后，窗口所有元素的個數依然滿足need要求，說明還可以繼續收縮，一直收縮到不滿足為止。

框架

  解題框架：while(right<s.size())1.移入右側元素，擴大窗口2.對新移入的元素進行判斷（1）它是need中的嗎？如果是，對window中該元素的個數記錄進行更新（1.1）該元素的增加，是否導致它的個數滿足了need的要求？如果是，valid+13.如果window中所有元素的個數都滿足了need要求（valid==need.size()），說明可以對左邊界進行收縮，以尋求更短的符合長度3.1對【最短覆蓋子串】的起始位置和長度進行更新3.2移出左側元素，縮小窗口3.3對移出的元素進行判斷（1）它是need中的嗎？如果是（1.1）該元素的減少是否導致其個數不再符合need要求？（因為可能該字符的個數超過need要求，導致減少一個以后依然滿足）如果不再滿足，valid-1對window中該元素的個數記錄進行更新（window記錄需要先進行上一步的判斷，所以判斷完以后再更新）