滑动窗口做题笔记
模板
/* 滑动窗口算法框架 */ void slidingWindow(string s) { unordered_map<char, int> window; int left = 0, right = 0; while (right < s.size()) { // c 是将移入窗口的字符 char c = s[right]; // 增大窗口 right++; // 进行窗口内数据的一系列更新 ... /*** debug 输出的位置 ***/ printf("window: [%d, %d)\n", left, right); /********************/ // 判断左侧窗口是否要收缩 while (window needs shrink) { // d 是将移出窗口的字符 char d = s[left]; // 缩小窗口 left++; // 进行窗口内数据的一系列更新 ... } } }
最小覆盖子串
string minWindow(string s, string t) { unordered_map<char, int> need, window; for (char c : t) need[c]++; int left = 0, right = 0; int valid = 0; // 记录最小覆盖子串的起始索引及长度 int start = 0, len = INT_MAX; while (right < s.size()) { // c 是将移入窗口的字符 char c = s[right]; // 扩大窗口 right++; // 进行窗口内数据的一系列更新 if (need.count(c)) { window[c]++; if (window[c] == need[c]) valid++; } // 判断左侧窗口是否要收缩 while (valid == need.size()) { // 在这里更新最小覆盖子串 if (right - left < len) { start = left; len = right - left; } // d 是将移出窗口的字符 char d = s[left]; // 缩小窗口 left++; // 进行窗口内数据的一系列更新 if (need.count(d)) { if (window[d] == need[d]) valid--; window[d]--; } } } // 返回最小覆盖子串 return len == INT_MAX ? "" : s.substr(start, len); }
找到字符串中所有字母异位词
class Solution { public: vector<int> findAnagrams(string s, string p) { unordered_map<char,int> need,window; for(char c:p) need[c]++; int left,right; left = right = 0; int valid = 0; //1. vector<int> res; while(right<s.size()) { char r = s[right]; right++; if(need.count(r)){ window[r]++; if(need[r]==window[r]){ valid++; } } while(right-left>=p.size()) { if(valid==need.size()){ res.push_back(left); } char L = s[left]; left++; if(need.count(L)){ if(need[L]==window[L]){ valid--; } window[L]--; } } } return res; } };
无重复字符的最长子串
class Solution { public: int lengthOfLongestSubstring(string s) { unordered_map<char,int> window; int left,right;left = right = 0; int res = 0; while(right<s.size()) { char r = s[right]; right++; window[r]++; while(window[r]>1){ char L = s[left]; window[L]--; left++; } res = max(res,right-left); } return res; } };