?滑动窗口算法模板：
for(int i=0,j=0;i<n;i++){
i下标加入滑动窗口
while(j<=i&&check(i,j)){
j++;
j下标移除滑动窗口
}
更新答案
}解释：
每次for循环，i++，表示i指针向后移动一位，while是找和 i 匹配，在i左面最远的合法 的下标 j。
?（ 如果求最小值，那 么 while 就是找和 j 匹配，在i左面最近的合法下标? j? ?）
所以 while 循环的作用是在i向右移动一位后，使滑动窗口合法。
在滑动窗口合法后更新答案。
先把这个模板写下来，然后再想每道题目如何做。
双指针算法的本质：优化循化
O（n2）优化为O(n)
性质：i，j的移动一般具有单调性。
i向后移动时，j只能向后移动或者时不动，不能向前移动。
证明：
i 向后移动一个 i' ，假设满足 j 可以向左移动一位变成 j' ， 则 [ j' , i '] 满足性质，[j' , i] 满足性质, [j , i ] 满足性质，一般可以推出矛盾。
正是由于j的移动具有单调性，所以省去了指针回溯的操作，所以可以化简时间复杂度。
动态维护窗口：
需要用变量或者哈希表动态维护区间具有的性质。
常见的有：
●维护长度：i-j+1
●维护特殊元素个数：cnt
●区间中不包含重复元素：哈希表（可以使用数组模拟哈希表，常见的有ASCII码映射到下标），重复的元素只可能是新加进的元素
●区间中包含元素的排列：哈希表记录窗口中元素个数，用cnt维护个数相等的元素数。
例题：
3. Longest Substring Without Repeating Characters
Given a string s, find the length of the longest substring without repeating characters.
0 <= s.length <= 5 * 104
s consists of English letters, digits, symbols and spaces.
题意：找不含重复元素的最长的连续子串
动态维护区间：开一个数组c，记录字符在窗口中出现的次数（下标为字符的ASCII码）
符合条件的区间：没有重复的字符
由于当前区间已经 没有重复的字符，那么只有新加进窗口的字符可能出现重复
所以，判断没有重复的字符可以直接用c[s[i]]>1。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n=s.size();
if(s.size()==0)return 0;
int c[300];
memset(c,0,sizeof(c));
int res=0;
for(int i=0,j=0;i<n;i++){
c[s[i]]++;
while(c[s[i]]>1){
c[s[j]]--;
j++;
}
res=max(res,i-j+1);
}
return res;
}
};1456. Maximum Number of Vowels in a Substring of Given Length
Given a string s and an integer k, return the maximum number of vowel letters in any substring of s with length k.
Vowel letters in English are 'a', 'e', 'i', 'o', and 'u'.。
题意：求定长区间的元音字母的最大个数
符合题意的条件：i-j+1==k。
由于while向右寻找第一个符合条件的j，所以当不符合条件时，进行j++操作。
动态维护窗口：由于窗口中需要知道有几个元音字母，所以用一个变量来动态维护元音字母的个数。
当
class Solution {
public:
int maxVowels(string a, int k) {
int n=a.size();
int res=0;
int cnt=0;
for(int i=0,j=0;i<n;i++){
if(a[i]=='a'||a[i]=='e'||a[i]=='i'||a[i]=='o'||a[i]=='u')cnt++;
while(j<=i&&i-j+1>k){
if(a[j]=='a'||a[j]=='e'||a[j]=='i'||a[j]=='o'||a[j]=='u')cnt--;
j++;
}
res=max(res,cnt);
}
return res;
}
};209. Minimum Size Subarray Sum
Given an array of positive integers nums and a positive integer target, return the minimal length of a contiguous（连续的） subarray [numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater than or equal to target. If there is no such subarray, return 0 instead.
题意：给定正数数组和一个正整数target，求所有数之和大于等于target的最短区间
i向右走一个位置，j向右走到最后一个合法的位置。
sum-a[j]>=target:如果去掉a[j]后sum依然大于target，那么j向后移一位。
如果sum>target，则更新结果。
如果没有sum>target这个限制条件，那么会出现sum在没有target的情况下就更新了答案。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& a) {
int n=a.size();
int sum=0;
int res=0x3f3f3f3f;
for(int i=0,j=0;i<n;i++){
sum+=a[i];
//sum-a[j]表示去掉j下标的数后sum仍然大于target
while(j<=i&&sum-a[j]>=target){
sum-=a[j];
j++;
}
//必须保证sum大于target才能更新答案
if(sum>=target)res=min(res,i-j+1);
}
return res==0x3f3f3f3f?0:res;
}
};Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.
In other words, return true if one of s1's permutations is the substring of s2.
?s2中维护定长s1.size()的窗口，判断窗口中的字母是否是s1的排列。
只要判断窗口中字符的字符数是否与s1中字符的字符数相等。
使用cnt记录字符个数相等的字符数。
只要cnt等于s1中不同字符个数即可。
动态维护cnt
class Solution {
public:
//S1存放s1中字符出现的次数
//S2存放s2的窗口中字符出现的次数
unordered_map<char,int>S1,S2;
bool check(char c){
return S1.count(c)&&S1[c]==S2[c];
}
bool checkInclusion(string s1, string s2) {
for(int i=0;i<s1.size();i++){
S1[s1[i]]++;
}
//cnt维护窗口中字符和s2字符个数相等的字符数
for(int i=0,j=0,cnt=0;i<s2.size();i++){
//如果S2中s1[i]出现的次数等于S1窗口中s1[i]出现的次数，那么在窗口拓展时，窗口中s1[i]出现的次数会+1，cnt要-1
if(check(s2[i]))cnt--;
S2[s2[i]]++;
//如果加1后相等，更新cnt
if(check(s2[i]))cnt++;
while(j<=i&&i-j+1>s1.size()){
if(check(s2[j]))cnt--;
S2[s2[j]]--;
if(check(s2[j]))cnt++;
j++;
}
if(cnt==S1.size())return true;
}
return false;
}
};438. Find All Anagrams in a String
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
题意：找出s中所有p的变位词的开始下标
同leetcode567。
class Solution {
public:
unordered_map<char ,int>S,P;
bool check(char c){
return S.count(c)&&S[c]==P[c];
}
vector<int> findAnagrams(string s, string p) {
vector<int>res;
for(int i=0;i<p.size();i++){
P[p[i]]++;
}
for(int i=0,j=0,cnt=0;i<s.size();i++){
if(check(s[i]))cnt--;
S[s[i]]++;
if(check(s[i]))cnt++;
while(j<=i&&i-j+1>p.size()){
if(check(s[j]))cnt--;
S[s[j]]--;
if(check(s[j]))cnt++;
j++;
}
if(cnt==P.size())res.push_back(j);
}
return res;
}
};