一、题目描述
给定两个字符串 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仅包含小写字母
二、解题思路
对于这种匹配连续字符串的题目，首先考虑就是滑动窗口的解法。
我们一般使用左右两个指针表示窗口窗口的两端，一开始的时候，窗口中没有一个元素，此时要做就是移动右指针，往窗口中添加元素。
当窗口中的元素数量等于需要匹配的字符串长度时，需要判断窗口中的字符串是否满足匹配条件，如果满足则记录结果。
不管窗口中的字符串是否满足匹配结果，此时都需要往右移动窗口了（先移动左指针，后移动右指针），然后开始下一次的判断。
示例代码
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
int[] needs = new int[123];
for (int i = 0; i < p.length(); i++) {
++needs[p.charAt(i)];
}
int[] count = new int[123];
int left = 0;
int right = 0;
while (right < s.length()) {
char c = s.charAt(right++);
++count[c];
if (right - left == p.length() && checkArr(needs, count, p)) {
result.add(left);
}
if (right - left >= p.length()) {
--count[s.charAt(left)];
++left;
}
}
return result;
}
public boolean checkArr(int[] needs, int[] count, String p) {
for (int i = 0; i < p.length(); i++) {
char c = p.charAt(i);
if (needs[c] != count[c]) {
return false;
}
}
return true;
}
}上面的代码虽然在 LeetCode 上面通过，但是结果并不优雅，耗时太多了。这里面有一个致命的问题，就是每次移动窗口的都会调用一个方法判断窗口中的字符数量是否等于匹配需要的字符数量。假设字符串s的长度为m，字符串p的长度为n，那么这里的时间复杂度接近O(m*n)，已经很糟糕了
那么是不是还有更加优雅的解法呢？
我们可以换一种方法，使用一个变量记录已经匹配的字符数量，而不是每次都去比较获取结果，这有点使用空间换时间的味道了。这样可以大幅度减少循环里面的运算次数，降低时间消耗。
示例代码
class Solution {
public List<Integer> findAnagrams(String s, String p) {
// 记录结果
List<Integer> result = new ArrayList<>();
// 记录匹配字符串p需要的字符数量
int[] needs = new int[123];
for (int i = 0; i < p.length(); i++) {
++needs[p.charAt(i)];
}
// 记录窗口中字符的数量，窗口是一个左闭右开的区间
int[] window = new int[123];
// 左边指针的位置
int left = 0;
// 右边指针的位置
int right = 0;
// 记录匹配的有效字符串数量（假设需要两个a，窗口中出现了三个a，只会记录两个a的数量）
int valid = 0;
while (right < s.length()) {
char r = s.charAt(right++);
// 当字符串是构建字符串p需要的字符时，窗口中对应的字符记录数+1
if (needs[r] != 0) {
++window[r];
// 当窗口中的字符数量少于等于需要的字符数量时，记录已经匹配的字符串长度的变量+1，当数量超过需要的数量时，不增加
if (window[r] <= needs[r]) {
++valid;
}
}
// 当窗口中的字符长度大于等于字符串p的长度时，开始移动窗口，也就是移动左指针
if (right - left >= p.length()) {
// 如果匹配的字符串长度已经等于字符串p的长度时，记录结果
if (valid == p.length()) {
result.add(left);
}
char l = s.charAt(left++);
// 与上面添加的操作相反，如果字符串是构建字符串p需要的字符时，此时窗口中对应字符记录数-1
if (needs[l] != 0) {
// 与上面添加的操作相反，上面增加的数量，此时移动窗口移除字符时也需要让匹配字符的数量-1，超过数量的字符不处理
if (window[l] <= needs[l]) {
--valid;
}
--window[l];
}
}
}
return result;
}
}三、总结
滑动窗口的思想很容易理解，但是实现起来并没有那么简单。简单的说细节是魔鬼。
- 为了耗时少，要尽可能的减少循环内的运算次数。
- 窗口是一个左闭右开的区间，即
[left,right) - 窗口滑动的过程中，添加字符的过程中修改了多少数据，移除字符的时候也同样的要修改多少数据
- 判断匹配字符串数量
(window[l] <= needs[l])和改变窗口字符数量(--window[l])的先后顺序不能错乱
