题目：find-all-anagrams-in-a-string

给定两个字符串 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. 分别用 int[26] 数组来表示在字符串 p 和 s 里面26个字母各自的出现次数
2. 初始化 p ，放进 int[26] 里 ，与此同时，初始化 s 的前 p 个字母，做第一次比较
3. 之后， 开两个变量 left 和 right，开始滑动比较，滑动窗口大小固定为 p 的长度，对 s 进行滑动，一旦代表 p 的数组和代表 s 的数组一样，结果 + 1
4. 代表 p 的数组和代表 s 的数组，长度一直都是一样长的，区别只在于里面每个下标的数字，表示每个字母出现的次数
5. p 数组在第一次遍历完后就不再变化了，我们滑动的是 s 数组

注意点：

• p.charAt(i) - 'a' 表示 p 的第 i 个字符，落到 int[26] 的下标，如果 p.charAt(i) 是 b ，那么 b - a = 1，落到 int[1] 的位置。

Java 实现

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> resultList = new ArrayList<>();
        if ( s == null || p == null || s.length() < p.length()){
            return resultList;
        }
        int[] pCount = new int[26];
        int[] sCount = new int[26];
        for (int i = 0; i < p.length(); i++){
            pCount[p.charAt(i) - 'a']++;
            sCount[s.charAt(i) - 'a']++;
        }
        if (Arrays.equals(pCount, sCount)){
            resultList.add(0);
        }
        int left = 0;
        for (int right = p.length() ; right < s.length(); right++){
            // 窗口向右滑动一位：移入右侧的新字符，移出左侧的旧字符
            sCount[s.charAt(right) - 'a']++;
            sCount[s.charAt(left) - 'a']--;
            left++;
            if (Arrays.equals(pCount, sCount)){
                resultList.add(left);
            }
        }
        return resultList;
    }
}