1. 題目

給你一個字符串 S、一個字符串 T，請在字符串 S 里面找出：包含 T 所有字母的最小子串。

示例： 輸入: S = "ADOBECODEBANC", T = "ABC" 輸出: "BANC"說明： 如果 S 中不存這樣的子串，則返回空字符串 ""。 如果 S 中存在這樣的子串，我們保證它是唯一的答案。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-window-substring
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 滑動窗口

類似題目：LeetCode 727. 最小窗口子序列（滑動窗口）

• 對t中的字符計數
• 設置窗口（left，right），一開始right右移，直到窗口包含所有t中字符
• 然后開始右移左端點，字符移除，直到有效的t字符數不夠了，再返回上面循環，右移右端點

class Solution { public:string minWindow(string s, string t) {if(s == "" || t == "" || s.size() < t.size())return "";unordered_map<char,int> m;for(char c : t)m[c]++;string ans;int left = 0, right = 0, len = 0, minLen = INT_MAX;for( ; right < s.size(); ++right){m[s[right]]--;//希望t中的字符計數為0（為正，說明還不夠，為負，說明多了）if(m[s[right]]>=0)//不存在t中的字符計數是負的，存在t中，且多出的，計數也為負++len;while(len == t.size())//窗口包含所有的t的字符了{if(right-left+1 < minLen)//更新最小窗口長度{minLen = right-left+1;ans = s.substr(left,minLen);}m[s[left]]++;//縮短left，計數+1(非t字符趨近0，t中字符計數由-或者0往上增加)if(m[s[left]] > 0)//t中的字符才有可能大于0（目標t字符數不夠）--len;//窗口包含t的字符數-1left++;//縮短左窗口，直到len不等于t的長度（有效字符數不夠了）}}return ans;} };

總結

以上是生活随笔為你收集整理的LeetCode 76. 最小覆盖子串（滑动窗口）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。