滑动窗口算法框架：移动右侧窗口，进行窗口内数据的一系列更新；判断左侧窗口是否需要收缩，再左移窗口，进行窗口内数据的一系列更新。
/* 滑动窗口算法框架 */ void slidingWindow(string s, string t) { unordered_map<char, int> need, window; for (char c : t) need[c]++; int left = 0, right = 0; int valid = 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++; // 进行窗口内数据的一系列更新 ... } } }其中两处...表示的更新窗口数据的地方，根据题目直接往里面填就行了。下面是四道例题，在框架基础上进行填充。
1、最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
示例：
输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC" 说明：
如果 S 中不存这样的子串，则返回空字符串 ""。如果 S 中存在这样的子串，我们保证它是唯一的答案。
class Solution { public: string minWindow(string s, string t) { unordered_map<char,int> need,window; //need记录需要包含的所有字符及其个数 for(char c:t) need[c]++; int left = 0,right = 0; int valid = 0;//窗口中满足need条件的字符个数 //记录最小覆盖子串的起始索引和长度 int start = 0,len = INT_MAX; while(right<s.size()) { 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; } 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); } };2、字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba").
示例2:
输入: s1= "ab" s2 = "eidboaoo" 输出: False
class Solution { public: bool checkInclusion(string s1, string s2) { unordered_map<char,int>need,window; for(int c:s1) need[c]++; int left = 0,right = 0; int valid = 0; while(right<s2.size()) { char c = s2[right]; right++; if(need.count(c)) { window[c]++; if(window[c]==need[c]) valid++; } while(right-left >= s1.size()) { if(valid == need.size()) return true; char d = s2[left]; left++; if(need.count(d)) { if(window[d]==need[d]) valid--; window[d]--; } } } return false; } };3、找到字符串中所有字母异位词
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
字母异位词指字母相同，但排列不同的字符串。不考虑答案输出的顺序。 示例 1:
输入:s: "cbaebabacd" p: "abc"
输出:[0, 6]
解释:起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
class Solution { public: vector<int> findAnagrams(string s, string p) { unordered_map<char,int>need,window; vector<int> res; for(int c:p) need[c]++; int left = 0,right = 0; int valid = 0; int start;//记录起始索引 while(right<s.size()) { char c = s[right]; right++; if(need.count(c)) { window[c]++; if(window[c] == need[c]) valid++; } while(right-left >= p.size()) { if(valid == need.size()) { start = left; res.push_back(start); } char d = s[left]; left++; if(need.count(d)) { if(window[d]==need[d]) valid--; window[d]--; } } } return res; } };4、无重复字符的最大子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
class Solution { public: int lengthOfLongestSubstring(string s) { if(s.size() == 0) return 0; unordered_map<char,int>window; int left = 0, right = 0; int len = 0; while(right<s.size()) { char c = s[right]; right++; window[c]++; while(window[c]>1)//有重复字符，移动左窗，使窗口内无重复字符 { char d = s[left]; left++; window[d]--; } len = max(len,right-left);//更新结果 } return len; } };
