?本题思路：
我们在字符串?S?中使用双指针中的左右指针技巧，初始化?left = right = 0，把索引左闭右开区间?[left, right)?称为一个「窗口」。
PS：理论上你可以设计两端都开或者两端都闭的区间，但设计为左闭右开区间是最方便处理的。因为这样初始化?
left = right = 0?时区间?[0, 0)?中没有元素，但只要让?right?向右移动（扩大）一位，区间?[0, 1)?就包含一个元素?0?了。如果你设置为两端都开的区间，那么让?right?向右移动一位后开区间?(0, 1)?仍然没有元素；如果你设置为两端都闭的区间，那么初始区间?[0, 0]?就包含了一个元素。这两种情况都会给边界处理带来不必要的麻烦。
2、我们先不断地增加?right?指针扩大窗口?[left, right)，直到窗口中的字符串符合要求（包含了?T?中的所有字符）。
3、此时，我们停止增加?right，转而不断增加?left?指针缩小窗口?[left, right)，直到窗口中的字符串不再符合要求（不包含?T?中的所有字符了）。同时，每次增加?left，我们都要更新一轮结果。
4、重复第 2 和第 3 步，直到?right?到达字符串?S?的尽头。
这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。
下面画图理解一下，needs?和?window?相当于计数器，分别记录?T?中字符出现次数和「窗口」中的相应字符的出现次数。
初始状态：
?增加?right，直到窗口?[left, right)?包含了?T?中所有字符
现在开始增加?left，缩小窗口?[left, right)：?
直到窗口中的字符串不再符合要求，left?不再继续移动?
?
public String minWindow(String s, String t) {
Map<Character,Integer> window = new HashMap(); // 用来记录窗口中的字符和数量
Map<Character,Integer> need = new HashMap(); // 需要凑齐的字符和数量
// 构建need字符集
for (int i = 0; i < t.length(); i++) {
char needChar = t.charAt(i);
need.put(needChar,need.getOrDefault(needChar,0)+1);
}
int left = 0,right = 0,valid = 0;
// valid是用来记录窗口中满足need要求的字符和数量的数目，比如need中要求字符a数量为2，如果window中的a字符的数量等于了2，valid就＋1，反之-1
int len = Integer.MAX_VALUE; // 记录最小字串的长度
int start = 0; // 记录最小字串的起始位置
while(right < s.length()){
char addChar = s.charAt(right); // 即将要加入window的字符
window.put(addChar,window.getOrDefault(addChar,0) + 1);
right++;
// 如果加入的字符是need中要求的字符，并且数量已经达到了need要求的数量，则valid+1
// 这里和下面都有个坑，window.get(addChar)和need.get(addChar)返回的都是对象，最好用.equals()方法比较大小
if(need.containsKey(addChar) && window.get(addChar).equals(need.get(addChar))){
valid++;
}
// 当window中记录的字符和数量满足了need中要求的字符和数量，考虑缩窗口
while(valid == need.size()){
// 先判断当前的最小覆盖字串是否比之前的最小覆盖字串短
if(right - left < len){ // 注意，这里上面已经对right实施了++操作，所以这里的长度不是right - left + 1
len = right - left ;
start = left; // 如果最短，则记录下该最小覆盖字串的起始位置
}
char removeChar = s.charAt(left);
// 开始缩减窗口，left右移，如果要从window删除的字符正好是need中需要的并且，数目也等于need中需要的数目，则删减后，该该字符要求的数量
// 显然不满足need要求的数量，所以valid要-1；
if(need.containsKey(removeChar) && window.get(removeChar).equals(need.get(removeChar))){
valid--;
}
window.put(removeChar,window.get(removeChar) - 1);
left++;
}
}
// 如果最小覆盖字串的长度相对于定义时没变，则t不包含s中所有的字符，返回"",如果长度改变过，说明存在这样的最小覆盖字串，直接输出。
return len == Integer.MAX_VALUE?"":s.substring(start,start+len);
}
?
public boolean checkInclusion(String s1, String s2) {
int sz = s2.length();
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for(char c : s1.toCharArray()){
need.put(c, need.getOrDefault(c,0)+1);
}
int left = 0, right = 0;
int valid = 0;
while(right < sz){
//进来的字符
char c = s2.charAt(right);
right++; //扩大窗口
//改变窗口状态
if(need.containsKey(c)){
window.put(c, window.getOrDefault(c,0)+1);
if(window.get(c).equals(need.get(c))) valid++;
}
//判断是否要收缩
while(valid == need.size()){
//子串包含s1的全部字符 且 长度相等 即 满足题意
if(right - left == s1.length()) return true;
//要移出的字符
char d = s2.charAt(left);
left++; //缩小窗口
//改变窗口状态
if(need.containsKey(d)){
if(window.get(d).equals(need.get(d))) valid--;
window.put(d, window.getOrDefault(d,0)-1);
}
}
}
return false;
}
?
public List<Integer> findAnagrams(String s, String p) {
//在长度为26的int数组target中存储字符串p中对应字符（a~z）出现的次数
//如p="abc",则target为[1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
//如p="bbdfeee",则target为[0,2,0,1,3,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
int[] target = new int[26];
for (int i = 0; i < p.length(); i++) {
target[p.charAt(i) - 'a']++;
}
//双指针构建滑动窗口原理：
//1.右指针right先向右滑动并在window中存储对应字符出现次数
//2.当左右指针间的字符数量（包括左右指针位置的字符）与p长度相同时开始比较
//3.比较完成后，左右指针均向右滑动一位，再次比较
//4.以后一直重复2、3，直到end指针走到字符串s的末尾
int left = 0, right = 0;
int[] window = new int[26];//构建一个与target类似的，存储了字符串s从left位置到right位置的窗口中字符对应出现次数的数组
List<Integer> ans = new ArrayList<Integer>();
while (right < s.length()) {
window[s.charAt(right) - 'a']++;//每次右指针right滑动，字符串s的right位置的字符出现次数加1
if (right - left + 1 == p.length()) {
if (Arrays.equals(window, target)) ans.add(left);//通过Arrays.equals方法，当window数组与target数组相等即为异或词
window[s.charAt(left) - 'a']--;//比较完成后，字符串s的left位置的字符出现次数减1（减1是因为左指针下一步要向右滑动）
left++;//左指针向右滑动
}
right++;//右指针向右滑动
}
return ans;
}
?
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> window=new HashMap<>();
int left =0,right=0;
int res=0;
while (right<s.length()){
char c = s.charAt(right);
right++;
window.put(c,window.getOrDefault(c,0)+1);
while (window.get(c)>1){
char c1 = s.charAt(left);
left++;
window.put(c1,window.get(c1)-1);
}
res=Math.max(res,right-left);
}
return res;
}
