眉山营销型网站建设,网站设计 注意,网页设计尺寸竖版,网站建设全网营销客户资源双指针的特殊应用#xff1a;滑动窗口
代码
题目链接#xff1a;https://leetcode.cn/problems/minimum-window-substring/description/ 不说废话#xff0c;直接贴代码#xff1a;
static string minWindow(string s, string t) {// need记录需要匹配的字符串t中每个字…双指针的特殊应用滑动窗口
代码
题目链接https://leetcode.cn/problems/minimum-window-substring/description/ 不说废话直接贴代码
static string minWindow(string s, string t) {// need记录需要匹配的字符串t中每个字符及出现的次数// window记录s中维护的窗口中对应need字符出现的次数记录其他字符没有用unordered_mapchar, 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(rights.size())1.移入右侧元素扩大窗口2.对新移入的元素进行判断1它是need中的吗如果是对window中该元素的个数记录进行更新1.1该元素的增加是否导致它的个数满足了need的要求如果是valid13.如果window中所有元素的个数都满足了need要求validneed.size()说明可以对左边界进行收缩以寻求更短的符合长度3.1对【最短覆盖子串】的起始位置和长度进行更新3.2移出左侧元素缩小窗口3.3对移出的元素进行判断1它是need中的吗如果是1.1该元素的减少是否导致其个数不再符合need要求因为可能该字符的个数超过need要求导致减少一个以后依然满足如果不再满足valid-1对window中该元素的个数记录进行更新window记录需要先进行上一步的判断所以判断完以后再更新
