一、题目
给定两个字符串?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" 的异位词。
二、思路解析
这道题的关键在于，想到利用一个 变量?count 来记录窗口中的 「有效字符」 个数。
而有效数字存在的前提，就是 s?中每一个字符的出现次数，一定不能超过 p 中对应符的出现次数，否则就不是题目要求的子串了。
这道题我用了 2 个数组，来记录 s 和 p 中每个字符的出现次数，其中数组下标为字符的 ACII 码值。
剩下的就是滑动窗口的实现跟维护、 count 的维护，以及结果的更新了，具体步骤我也有在下面代码注释中写到啦。
三、完整代码
class Solution {
public List<Integer> findAnagrams(String ss, String pp) {
char[] s = ss.toCharArray();
char[] p = pp.toCharArray();
int n = s.length;
int m = p.length;
List<Integer> ret = new ArrayList<Integer>();
//记录 p 中每个字符的出现次数，其中数组下标为字符的 ACII 码值
int[] hash1 = new int [26];
for(char ch : p){
hash1[ch - 'a']++;
}
//滑动窗口
int[] hash2 = new int [26];
for(int left = 0 , right = 0 , count = 0; right < n ; right ++){
char in = s[right];
//count 用于记录有效字符「即 s 字符串中的 a 字符数量 <= p 字符串中的 a 字符数量」
if(++hash2[in - 'a'] <= hash1[in - 'a']){
count ++;
}
//进入窗口 + 维护 count
if(right - left + 1 > m){
char out = s[left++];
if(hash2[out - 'a']-- <= hash1[out - 'a'] ){
count --;
}
}
//出窗口 + 维护 count
//更新结果
if(count == m){
ret.add(left);
}
}
return ret;
}
}以上就是本篇博客的全部内容啦，如有不足之处，还请各位指出，期待能和各位一起进步！