力扣-找到字符串中所有字母异位符-EW帮帮网

1.题目描述

2.题目链接

LCR 015. 找到字符串中所有字母异位词 - 力扣（LeetCode）

3.代码解答

class Solution {
    public List<Integer> findAnagrams(String ss, String pp) {
        char[]s=ss.toCharArray();
        char[]p=pp.toCharArray();
        List<Integer>ret=new ArrayList<>();
        int[]hash1=new int[26];
        int[]hash2=new int[26];
        for(char ps:p){
            hash1[ps-'a']++;
        }
        int plen=p.length;
        for(int left=0,right=0,count=0;right<s.length;right++){
            char in=s[right],out=s[left];
            if(++hash2[in-'a']<=hash1[in-'a']){
                count++;
            }
            if(right-left+1>plen){
                if(hash2[out-'a']--<=hash1[out-'a']){
                    count--;
                }
                left++;
            }
            if(count==plen){
                ret.add(left);
            }
           
        }
        return ret;
    }
}

4.解题思路

1）先将两个字符串转为字符数组，方便后续使用。并定义一个ArrayList作为结果数组来存放所有满足条件的字母异位符的起始下标，定义两个26位的hash数组来存放字符数组s和p。

2）将p中的所有字符都存放到hash数组中，数组下标就是p中的字符-‘a’得到的asci码值的差值，数组的值对应p中该字符的个数。

3）使用滑动窗口来解决问题。定义两个滑动指针，均指向首元素。定义一个int类型的变量count来存放s字符串中left到right之间的字符串中满足p要求的个数。如果个数超过，则不增加。

比如left到right之间的字符串rets是aba，p字符串为a，rets有2个a，但是count==1。

4)使用right指针遍历数组，将right下标的元素挨个存入hash数组中，如果遇到s字符串中left到right之间的字符，count++。

5）如果left到right之间长度超过了p字符串的长度，则一定不符合要求，left++。但是这里要判断一下，left++后count变量的值是否会受影响，如果left++后rets字符串中有效字符的个数减少了，count--。

6）遇到count==plen时，将left存入结果数组中。

5.代码细节

1）使用toCharArray方法来将字符串转为字符数组

  char[]s=ss.toCharArray();
  char[]p=pp.toCharArray();

2）使用数组来代替真正的哈希表

        int[]hash1=new int[26];
        int[]hash2=new int[26];

3)使用ps-'a'来找到字符对应的哈希数组位置下标

for(char ps:p){
            hash1[ps-'a']++;
        }

4）使用if循环而不是while循环

 if(right-left+1>plen)
{
  if(hash2[out-'a']--<=hash1[out-'a'])
   {
      count--;
   }
    left++;
}

假如使用while循环：left指针会持续移动直到窗口长度合法。但是由于right是逐步移动，所以只可能超出1步，不存在超出多个字符的情况，left也就不存在连续移动的情况，所以只能使用if循环。

5）hash2[out-'a']--而不是--hash2[out-'a']

if(right-left+1>plen){
  if(hash2[out-'a']--<=hash1[out-'a']){
                    count--;
        }
    left++;
 }

执行步骤：
1. 比较：hash2[out-'a'] <= hash1[out-'a']（使用当前值比较）。
2. 自减：hash2[out-'a'] 的值减 1。
含义：
若移出前的字符频率已经等于或小于目标频率（即 hash2 <= hash1），说明移出后该字符的有效计数减少，因此 count--。
如果使用先减后用：
执行步骤：
1. 自减：hash2[out-'a'] 的值减 1。
2. 比较：hash2[out-'a'] <= hash1[out-'a']（使用减 1 后的值比较）。
问题：
若移出前的字符频率恰好比目标频率多 1（即 hash2 == hash1 + 1），前缀自减会先将 hash2 减 1，导致比较结果变为 hash2 == hash1，从而错误地触发 count--。实际上，移出前该字符的频率未超限（hash2 > hash1），移出后才变为合法（hash2 == hash1），但前缀自减掩盖了这一事实。

力扣-找到字符串中所有字母异位符