438. 找到字符串中所有字母异位词
438. 找到字符串中所有字母异位词
分析
这个题跟 76. 最小覆盖子串 非常像，但是，其实不适合套用最小覆盖子串的模板，因为最小覆盖子串是求不定长子串的，而这个题求得是固定长度的子串，因此我们可以用固定间隔的双指针来解决这个问题。即一次同时移动左右边界，而不是跟最小覆盖子串一样一次只移动一个左边界或者一个右边界。
使用滑动窗口的时候，我们在一次循环的时候，根据条件移动一次左指针或者右指针，但是双指针法不是的，双指针法在一次循环中可能会同时移动左右指针
核心逻辑依然是：先将字符转化为整数，然后用 int[] 数组来记录整个字符串中的字符出现的次数，p 用 pMap 记录，在遍历 s 之前，我们就需要把 pMap 初始化好，s 的子串用 sMap 记录，同时，为了快速比较 s 的子串跟 p 是否相等，我们需要用一个 count 变量来保存 目标字符串中的字符，在当前子数组中的出现个数，在刚开始 while 循环的时候，因为 [left,right]) 字串的长度还没有 p 的长度那么长，所以一开始只移动 right 指针，更新 count 和 sMap，当 [left,right]) 字串的长度到达 p 的长度之后，就同时移动 left 和 right，同时更新 count，一次循环之后，如果 count 为 p 的长度，则可以将 left 添加到 result 列表中。循环结束的条件就是 right==s.length()
快指针移动的时候，count，sMap 的更新逻辑
if(pMap[sArr[right]-offset]>0){
if(sMap[sArr[right]-offset]<pMap[sArr[right]-offset]){
count++;
}
sMap[sArr[right]-offset]++;
}
慢指针移动的时候，count，sMap 的更新逻辑
if(pMap[sArr[left]-offset]>0){
if(sMap[sArr[left]-offset]<=pMap[sArr[left]-offset]){
count--;
}
sMap[sArr[left]-offset]--;
}
简单来说，count 的更新方式是
- 移动快指针的时候，如果新加入的字符在子串中出现的次数小于字符在 p 中出现的次数，
count++ - 移动慢指针的时候，如果移除的字符在子串中出现的次数小于等于字符在 p 中出现的次数，
count--;
解题
注意 slow 和 fast 的定义，在第一步从 0 移动 fast 结束的那个 for 循环，我们要清楚此时 fast 指向的是谁，slow 指向的是谁
class Solution {
public static int offset = 'a';
public static int asize = 26;
public List<Integer> findAnagrams(String s, String p) {
int[] pMap = new int[asize];
int[] sMap = new int[asize];
char[] pArr = p.toCharArray();
char[] sArr = s.toCharArray();
// 先统计p中字符出现的次数
int psize = p.length();
for(int i=0;i<psize;i++){
pMap[pArr[i]-offset]++;
}
// [left,right)
int left=0,right=0;
int count=0;
List<Integer> result = new ArrayList<>();
while(right<s.length()){
if(pMap[sArr[right]-offset]>0){
if(sMap[sArr[right]-offset]<pMap[sArr[right]-offset]){
count++;
}
sMap[sArr[right]-offset]++;
}
right++;
// 刚进入这个循环的时候 [left,right)为 [0,3)，
// 经过上面的 right++ ，right为4
// 假设 psize 为 3 ， right此时为4，那么 left 就需要移动了，left+1，为1 于是下一轮操作的时候，[left,right)为 [1,4)
if(right-left>psize){
if(pMap[sArr[left]-offset]>0){
if(sMap[sArr[left]-offset]<=pMap[sArr[left]-offset]){
count--;
}
sMap[sArr[left]-offset]--;
}
left++;
}
if(count==psize){
result.add(left);
}
}
return result;
}
}
这种遍历字符串，然后获取判断固定长度子串的写法，可以换种写法
for(int i=0;i<nums.length;i++){
// k 为固定子串的长度
if(i<k){
//
if(i==k-1){
//
}
continue;
}
// 左侧 i-k 右侧 i-1
}
可以参考 239. 滑动窗口最大值
后面我开始学习另一个种写法
[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;
}