滑动窗口技巧

滑动窗口算法的抽象思想

int left = 0, right = 0;while (right < s.size()) {window.add(s[right]);right++;while (valid) {//满足条件window.remove(s[left]);left++;}
}

unordered_map 就是哈希表（字典），它的一个方法 count(key) 相当于 containsKey(key) 可以判断键 key 是否存在。

可以使用方括号访问键对应的值 map[key]。需要注意的是，如果该 key 不存在，C++ 会自动创建这个 key，并把 map[key] 赋值为 0。

所以代码中多次出现的 map[key]++ 相当于 Java 的 map.put(key, map.getOrDefault(key, 0) + 1)。

1.最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。示例：输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

如何判断 window 即子串 s[left…right] 是否符合要求，是否包含 t 的所有字符呢？
可以用两个哈希表当作计数器解决。用一个哈希表 needs 记录字符串 t 中包含的字符及出现次数，用另一个哈希表 window 记录当前「窗口」中包含的字符及出现的次数，如果 window 包含所有 needs 中的键，且这些键对应的值都大于等于 needs 中的值，那么就可以知道当前「窗口」符合要求了，可以开始移动 left 指针了。

class Solution {
public:string minWindow(string s, string t) {if(s.empty()||t.empty())return "";unordered_map<char,int>window;//滑动窗口，存储s中有效字符和出现的次数unordered_map<char,int>needs;//存储t中有效字符和出现的次数int slow=0;int fast=0;int start=0;//目标索引int match=0;//记录s中有效元素并且有效元素的个数=有效字符的个数int minLength=INT_MAX;for(auto str:t)needs[str]++;int haveMatch=0;while(fast<s.size()){char rightchar=s[fast];if(needs.count(rightchar))//如果这个字符是有效字符{window[rightchar]++;//滑动窗口增加这个字符一次if(window[rightchar]==needs[rightchar])//如果这个字符出现次数也满足条件match++;}fast++;while(match==needs.size())//当满足条件{if(fast-slow<minLength)//替换最小字符串{start=slow;minLength=fast-slow;}char leftchar=s[slow];if(window.count(leftchar))//左指针缩小{window[leftchar]--;if(window[leftchar]<needs[leftchar])match--;}slow++;}}return minLength==INT_MAX? "":s.substr(start,minLength);}
};

二、找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。说明：字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例 1:输入:
s: "cbaebabacd" p: "abc"输出:
[0, 6]解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。示例 2:输入:
s: "abab" p: "ab"输出:
[0, 1, 2]解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

class Solution {
public:vector<int> findAnagrams(string s, string p) {if(s.empty()||p.empty())return vector<int>();int match=0;//匹配字符数int left=0;int right=p.size()-1;unordered_map<char,int>window;unordered_map<char,int>needs;//p中字符vector<int>ret;for(auto str:p)needs[str]++;//p中的字符和出现次数for(int i=0;i<p.size();i++)//先设置滑动窗口初始状态{if(needs.count(s[i])){window[s[i]]++;if(window[s[i]]==needs[s[i]])match++;}}while(right<s.size())//先移动左指针，后移动右指针{if(match==needs.size())//符合要求ret.push_back(left);right++;if(needs.count(s[left]))//左指针右移{if(window[s[left]]==needs[s[left]]){match--;}window[s[left]]--;}left++;if(needs.count(s[right]))//右指针右移{window[s[right]]++;if(window[s[right]]==needs[s[right]])match++;}}return ret;}
};

无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 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.empty())return 0;int left=0;int right=0;int maxlength=0;unordered_map<char,int>window;while(right<s.size()){char c1=s[right];window[c1]++; right++;while(window[c1]>1)//当ci有重复，缩减左指针直到不重复{char c2=s[left];window[c2]--;left++;}maxlength=max(maxlength,right-left);}return maxlength;}
};