438. 找到字符串中所有字母异位词
438. 找到字符串中所有字母异位词
分析
这个题，跟 76. 最小覆盖子串 非常像，不过却更加的简单，因为 76 题要求最短的子串，而这个题寻找的是字母异位词，也就是说子串的长度是固定的，因此我们不需要像 76 题那样，移动快指针以满足条件，然后移动慢指针来缩短字符串，在这个题中，快指针和慢指针的距离是固定的。
这里重复一下解题思路，首先用一个数组记录目标字符串 p 中每个字符的出现次数，然后定义快指针指向 s 的头部然后，直接比较 s 的 [0,p.toCharArray().length-1] 的子串是否跟 p 是字母异位词，然后新建一个慢指针，指向 s 的第一个字符，然后同时移动快指针和慢指针，每移动一次，更新子串的字符出现次数，同时比较一下 [slow,fast) 这个范围的子串是否与 p 是字母异位词。
比较子串跟 p 是否是字母异位词的方式也很简单，用一个变量 t 表示 p 中的字符在子串中出现的次数，t 的累加方式也很简单
- 移动快指针的时候，如果新加入的字符在子串中出现的次数小于等于字符在 p 中出现的次数，
t++ - 移动慢指针的时候，如果移除的字符在子串中出现的次数等于字符在 p 中出现的次数，
t--;
思路跟很简单，和 76. 最小覆盖子串 是差不多的，但是最后写代码的时候还是卡了一下，我们还是要搞清楚 slow 和 fast 指针的含义，严格按照变量定义来写代码。
解题
注意 slow 和 fast 的定义，在第一步从 0 移动 fast 结束的那个 for 循环，我们要清楚此时 fast 指向的是谁，slow 指向的是谁
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<Integer>();
char[] pChars = p.toCharArray();
char[] sChars = s.toCharArray();
if(sChars.length<pChars.length){
return result;
}
int offset = (int)'a';
int[] charCount = new int[26];
for(int i=0;i<pChars.length;i++ ){
int charIndex = (int)pChars[i];
charCount[charIndex-offset]++;
}
int t=0;
int[] subStrCharCount = new int[26];
int fast=0;
// 先移动fast
for(;fast<pChars.length;fast++){
int charIndex = (int)sChars[fast];
if(charCount[charIndex-offset]>0){
// 是p中的字符才需要计数
subStrCharCount[charIndex-offset]++;
if(subStrCharCount[charIndex-offset]<=charCount[charIndex-offset]){
t++;
}
if(t==pChars.length){
result.add(0);
}
}
}
// 此时，fast =p.length
// 注意，fast指向的是子数组的右边界的下一个元素
// slow指向的是子数组的左边界
// 因此 子数组的范围是 [slow,fast)
int slow =0;
// 再同时移动fast和slow
while(fast<sChars.length){
// 处理 fast 指针
int fastCharIndex = (int)sChars[fast];
if(charCount[fastCharIndex-offset]>0){
// 是p中的字符才需要计数
subStrCharCount[fastCharIndex-offset]++;
if(subStrCharCount[fastCharIndex-offset]<=charCount[fastCharIndex-offset]){
t++;
}
}
// 处理 slow 指针
int slowCharIndex = (int)sChars[slow];
if(charCount[slowCharIndex-offset]>0){
// 是p中的字符才需要计数
subStrCharCount[slowCharIndex-offset]--;
if(subStrCharCount[slowCharIndex-offset]<charCount[slowCharIndex-offset]){
t--;
}
}
if(t==pChars.length){
result.add(slow+1);
}
slow++;
fast++;
}
return result;
}
后面我开始习惯另一个种写法
[left,right]确定子串的边界- 我们在扫描 s 中的字符的时候，如果发现不是 p 中的字符，可以直接跳过。count 和子串中的有效字符个数数组都可以不操作。
- 先把移动 fast 或者 slow 指针之后，对 count 和子串计数的操作做了，最后再移动 fast 或者 slow 指针，这样更自然一些。
- 在计算 count 和 子串中的有效字符个数的时候，先计算 count，再对子串中的有效字符个数进行操作，这样更加自然
- 移动 fast 的时候，如果移动之前的字符个数小于目标个数，那 count 就加 1，因为移动之后，就可能相等了
- 移动 slow 的时候，如果移动之前的字符个数小于等于目标个数，那 count 就减 1，因为移动之后，就可能小于了
一定要同时维护 count 和子串中的有效字符个数的数组，我老是忘记要维护子串中的有效字符个数数组。
public List<Integer> findAnagrams(String s, String p) {
if (s.length() < p.length()) {
return new ArrayList<>();
}
List<Integer> result = new ArrayList<>();
int offset = (int) 'a';
int[] scount = new int[26];
int[] pcount = new int[26];
char[] schar = s.toCharArray();
char[] pchar = p.toCharArray();
for (int i=0; i < pchar.length; i++) {
pcount[pchar[i] - offset]++;
}
int count = 0;
// [left,right] 表示子串
int right = pchar.length - 1, left = 0;
for (int i = 0; i <= right; i++) {
int index = schar[i] - offset;
if (pcount[index] > 0) {
if (scount[index] < pcount[index]) {
count++;
}
scount[index]++;
}
}
if (count == pchar.length) {
result.add(left);
}
while (right < schar.length) {
if (right + 1 >= schar.length) {
break;
}
int rightIndex = schar[right + 1] - offset;
if (pcount[rightIndex] > 0) {
if (scount[rightIndex] < pcount[rightIndex]) {
count++;
}
scount[rightIndex]++;
}
int leftIndex = schar[left] - offset;
if (pcount[leftIndex] > 0) {
if (scount[leftIndex] <= pcount[leftIndex]) {
count--;
}
scount[leftIndex]--;
}
if (count == pchar.length) {
result.add(left + 1);
}
// 同时移动
left++;
right++;
}
return result;
}