Java_滑动窗口_找到字符串中所有字母异位词
题目链接： leetcode.cn/problems/Va…
题目描述：
给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
变位词 指字母相同，但排列不同的字符串。
示例 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" 的变位词。
提示:
1 <= s.length, p.length <= 3 * 104s和p仅包含小写字母
题目解析
异位词就是所含的字母个数一样，但是排列顺序可以不一样。例如例一中的 s = "cbaebabacd", p = "abc"，"abc"的异位词可以为{"abc","acb","bac","bca","cab","cba"}。
简单介绍完题目后，我们就开始找思路，要从给定的字符串 s 中找到 p 的所有异位词的子串，这个子串其实就是子数组，这不又是从数组中找子数组嘛，我们先使用暴力解法，再使用滑动窗口试试看。
在使用什么方法之前，我们先解决一下核心问题： 怎样判断窗口中的字母是否为 p 的变位词？ 第一个方法是拿到词之后就进行排序，然后直接进行 equals 比较，想法是简单的，但是时间复杂度不一定能过。 第二个方法是对所有的字母进行计数，如果窗口中的各个字母的计数与 p 中的相同，那就必定是子串。这个方法是可行的
Ⅰ.暴力解法：
暴力解法还是两层循环，外层为 left，内层为 right。
right 每走一次的时候就将字母丢到一个容器中，将 key 所对应的 value++，但是当遇到重复字母，或者不属于 p 中的字母时，判断不成立，left++，right = left，这样暴力解法和之前的几题都是一样的，存在的问题也是一样的。问题就是在遇到条件不成立时，直接盲目的回头再走一圈如下图所示。
当 s[r] = c 时，条件不成立，此时 l++，再次循环，s[l] = c，r = l,但是容器中还是会存储两个 c ,这就是纯属在浪费时间，我们可以直接将容器中的 a，c 弹出，r 继续向下遍历，因为容器中只要有两个 c 就不可能满足 abc 异位词的条件。当然在遇到 e 的时候就要特殊处理了，因为 e 不在 p 中，所以 l 和 r 可以直接跳转到 b 再开始遍历。
接下来直接看优化方法吧，滑动窗口。
Ⅱ. 滑动窗口 1、进窗口 创建一个容器，将所遍历到的字母往里丢
2、判断窗口是否满足条件 这题的判断条件可能比以往的多，就像暴力解法中判断的一样，之前我们遇到的都是一个 while 循环判断加出窗口就完事了，现在还要多加一个 if，因为 s 中可能存在 p 中不存在的字母，这时候也就没必要一个个出窗口了，直接将窗口移动到这个字母的下一个字母就可以了。 所以此处的判断有两个： ①刚刚进窗口的字母在 p 中是否存在，如果不存在的话直接清空窗口，并且跳转到这个字母（不存在的这个字母）的下一个字母。 ②刚刚进窗口的字母的个数是否超过了 p 中字母的个数，如果超过了就进行出窗口操作。
3、出窗口 如果满足 2 中的②就出窗口。
4、更新结果 上述步骤都执行完之后，判断是否满足条件，如果满足，就更新结果。 以上就是所有思路，下面开始写代码
代码
class Solution {
public List<Integer> findAnagrams(String s, String p) {
//先将字符串转化为字符数组，方便下面遍历操作
char[] sArr = s.toCharArray();
char[] pArr = p.toCharArray();
//创建容器，记录字母个数
HashMap<Character,Integer> sMap = new HashMap<>();
HashMap<Character,Integer> pMap = new HashMap<>();
//清点p中字母个数
for(char i : pArr){
//pMap.getOrDefault(i,0)这一步是如果不存在这个key就创建一个，并且赋值value为0
pMap.put(i, pMap.getOrDefault(i,0) + 1);
}
//创建一个数组,记录起始坐标
List<Integer> result = new ArrayList<>();
//核心操作
for (int l = 0, r = 0; r < sArr.length; r++) {
//进窗口
sMap.put(sArr[r],sMap.getOrDefault(sArr[r],0) + 1);
//判断是否满足出窗口条件
if (!pMap.containsKey(sArr[r])) {
//将l跳转到此字母的下一个字母
l = r + 1;
//清空窗口
sMap.clear();
//直接下一次循环
continue;
}
//判断此字母的个数是否大于p中的此字母个数
while (sMap.get(sArr[r]) > pMap.get(sArr[r])){
//出窗口，直至满足上述条件
sMap.put(sArr[l],sMap.get(sArr[l]) - 1);
//如果有字母在此过程中个数变为0，直接remove掉,防止影响下面判断两个map是否相等
if (sMap.get(sArr[l]) == 0) sMap.remove(sArr[l]);
l++;
}
//判断是否满足更新结果条件
if (sMap.equals(pMap)) result.add(l);
}
return result;
}
}