给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例 1:
输入:
s: "cbaebabacd" p: "abc"
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
public List<Integer> findAnagrams(String s, String p) {
char[] arrS = s.toCharArray();
char[] arrP = p.toCharArray();
// 接收最后返回的结果
List<Integer> ans = new ArrayList<Integer>();
// 定义一个 needs 数组来看 arrP 中包含元素的个数
int[] needs = new int[26];
// 定义一个 window 数组来看滑动窗口中是否有 arrP 中的元素，并记录出现的个数
int[] window = new int[26];
// 先将 arrP 中的元素保存到 needs 数组中
for (int i = 0; i < arrP.length; i++) {
needs[arrP[i] - 'a'] += 1;
}
// 定义滑动窗口的两端
int left = 0;
int right = 0;
// 右窗口开始不断向右移动
while (right < arrS.length) {
int curR = arrS[right] - 'a';
right++;
// 将右窗口当前访问到的元素 curR 个数加 1
window[curR] += 1;
// 当 window 数组中 curR 比 needs 数组中对应元素的个数要多的时候就该移动左窗口指针
// cbaebabacd abc 为例，当right移动到e的时候 会一直循环 让left 走到e 才罢休 然后从e开始计算
while (window[curR] > needs[curR]) {
int curL = arrS[left] - 'a';
left++;
// 将左窗口当前访问到的元素 curL 个数减 1
window[curL] -= 1;
}
// 这里将所有符合要求的左窗口索引放入到了接收结果的 List 中
if (right - left == arrP.length) {
ans.add(left);
}
}
return ans;
}
第二种解法利用 total
public List<Integer> findAnagrams(String s, String p) {
if(s == null || s.length() == 0) return new ArrayList<>();
List<Integer> res = new ArrayList<>();
int[] needs = new int[26]; //由于都是小写字母，因此直接用26个长度的数组代替原来的HashMap
int[] window = new int[26];
int left = 0, right = 0, total = p.length(); //用total检测窗口中是否已经涵盖了p中的字符
for(char ch : p.toCharArray()){
needs[ch - 'a'] ++;
}
while(right < s.length()){
char chr = s.charAt(right);
if(needs[chr - 'a'] > 0){
window[chr - 'a'] ++;
if(window[chr - 'a'] <= needs[chr - 'a']){
total --;
}
}
while(total == 0){
if(right-left+1 == p.length()){
res.add(left);
}
char chl = s.charAt(left);
if(needs[chl - 'a'] > 0){
window[chl - 'a'] --;
if(window[chl - 'a'] < needs[chl - 'a']){
total ++;
}
}
left ++;
}
right ++;
}
return res;
}
解法相同的 还有
242. 有效的字母异位词
public boolean isAnagram(String s, String t) {
char[] sourceArr = s.toCharArray();
char[] targetArr = t.toCharArray();
if (sourceArr.length != targetArr.length) {
return false;
}
int[] sourceFreq = new int[256];
int[] targetFreq = new int[256];
for (int i = 0; i < targetArr.length; i++) {
targetFreq[targetArr[i]]++;
}
int total = sourceArr.length;
int left = 0;
int right = 0;
while (right < sourceArr.length) {
char currentCharIndex = sourceArr[right];
if (targetFreq[currentCharIndex] <= 0) {
return false;
}
sourceFreq[currentCharIndex]++;
if (sourceFreq[currentCharIndex] <= targetFreq[currentCharIndex]) {
total--;
} else {
return false;
}
while (total == 0) {
char leftCharIndex = sourceArr[left];
if (targetFreq[leftCharIndex] <= 0) {
return false;
}
sourceFreq[leftCharIndex]--;
if (sourceFreq[leftCharIndex] <= targetFreq[leftCharIndex]) {
total++;
}
left++;
}
right++;
}
return true;
}
