什么情况下会想到滑动窗口法：
任何题目如果没有思路其实都可以想一下暴力解法。这道题暴力解法思路简单：
遍历任意i，j，使得i和j之间的子串长度，等于p串的长度。该子串称之为x。该步复杂度为O（n）。
判断x是否与p是异位词。是的话，则把i加入答案中。该步复杂度为O（n）。
暴力法的复杂度为O（n^2）。显然不高效。
可以发现第二步其实做了很多不必要的操作，例如[i, j]和[i+1, j+1]两个子串在暴力法第二步中，需要各遍历一次，完全没必要。其实[i+1, j+1]完全可以在[i, j]的基础上做判断，也就是去掉头部的字符（i位置），加上尾部的字符（j+1位置）。这样第一步的复杂度可以降到O(1)。整体复杂度降到O(n)。已经得到信息不重复使用就浪费了，没必要重新搜集近乎相同的信息。这就是滑动窗口法。
滑动窗口法的特点是，一连串元素的信息，可以用常数时间推断出，该串整体移位后，新串信息。
所有滑动窗口问题，如果能从暴力法优化的角度思考，都不难想到。
无重复数字的最长子串
右边一直滑
当遇到包含了的，左边就一直滑，知道没有了
用一个hashset来保存字母，进行判断
class Solution {
public int lengthOfLongestSubstring(String s) {
char[] arr = s.toCharArray();
HashSet<Character> hashSet = new HashSet<>();
int left = 0;
int res = 0;
for(int right = 0;right < arr.length;right++){
while (hashSet.contains(arr[right])){
hashSet.remove(arr[left]);
left++;
}
hashSet.add(arr[right]);
res = Math.max(res,right-left+1);
}
return res;
}
}找到字符串中所有字母异位词
class Solution {
public List<Integer> findAnagrams(String s, String p) {
HashMap<Character,Integer> window = new HashMap<>();
HashMap<Character,Integer> need = new HashMap<>();
for(char c : p.toCharArray()){
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
List<Integer> res = new LinkedList<>();
while (right < s.length()){
char c = s.charAt(right);
right++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
//注意这里是p的len，不是need的，如果有多个重复的need就会小于p
while (right - left >= p.length()) {
if (right - left == p.length() && valid == need.size()) {
res.add(left);
}
char d = s.charAt(left);
left++;
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
return res;
}
}
