滑动窗口
滑动窗口这类问题一般需要用到 双指针 来进行求解，另外一类比较特殊则是需要用到特定的数据结构，像是 sorted_map。
后者有特定的题型，后面会列出来，但是，对于前者，题形变化非常的大，一般都是基于字符串和数组的，所以我们重点总结这种基于双指针的滑动窗口问题。
题目问法大致有这几种：
- 给两个字符串，一长一短，问其中短的是否在长的中满足一定的条件存在，例如：
- 求长的的最短子串，该子串必须涵盖短的的所有字符
- 短的的 anagram 在长的中出现的所有位置
- ...
- 给一个字符串或者数组，问这个字符串的子串或者子数组是否满足一定的条件，例如：
- 含有少于 k 个不同字符的最长子串
- 所有字符都只出现一次的最长子串
- ...
解题思路与模板
根据前面的描述，滑动窗口就是这类题目的重点，换句话说，窗口的移动 就是重点！
我们要控制前后指针的移动来控制窗口，这样的移动是有条件的，也就是要想清楚在什么情况下移动，在什么情况下保持不变。
我的思路是保证右指针每次往前移动一格，每次移动都会有新的一个元素进入窗口，这时条件可能就会发生改变，然后根据当前条件来决定左指针是否移动，以及移动多少格。
我写来一个模版在这里，可以参考：
public int slidingWindowTemplate(String[] a, ...) {// 输入参数有效性判断if (...) {...}// 申请一个散列，用于记录窗口中具体元素的个数情况// 这里用数组的形式呈现，也可以考虑其他数据结构int[] hash = new int[...];// 预处理(可省), 一般情况是改变 hash...// l 表示左指针// count 记录当前的条件，具体根据题目要求来定义// result 用来存放结果int l = 0, count = ..., result = ...;for (int r = 0; r < A.length; ++r) {// 更新新元素在散列中的数量hash[A[r]]--;// 根据窗口的变更结果来改变条件值if (hash[A[r]] == ...) {count++;}// 如果当前条件不满足，移动左指针直至条件满足为止while (count > K || ...) {...if (...) {count--;}hash[A[l]]++;l++;}// 更新结果results = ...}return results;
}具体题目分析与代码
1. 找到字符串中所有字母异位词
题目：
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100 。
代码：
public List<Integer> findAnagrams(String s, String p) {// 输入参数有效性判断if (s.length() < p.length()) {return new ArrayList<Integer>();}// 申请一个散列，用于记录窗口中具体元素的个数情况// 这里用数组的形式呈现，也可以考虑其他数据结构char[] sArr = s.toCharArray();char[] pArr = p.toCharArray();int[] hash = new int[26];for (int i = 0; i < pArr.length; ++i) {hash[pArr[i] - 'a']++;}// l 表示左指针// count 记录当前的条件，具体根据题目要求来定义// result 用来存放结果List<Integer> results = new ArrayList<>();int l = 0, count = 0, pLength = p.length();for (int r = 0; r < sArr.length; ++r) {// 更新新元素在散列中的数量hash[sArr[r] - 'a']--;// 根据窗口的变更结果来改变条件值if (hash[sArr[r] - 'a'] >= 0) {count++;}// 如果当前条件不满足，移动左指针直至条件满足为止if (r > pLength - 1) {hash[sArr[l] - 'a']++;if (hash[sArr[l] - 'a'] > 0) {count--;}l++;}// 更新结果if (count == pLength) {results.add(l);}}return results;
}