438找到字符串中所有字母异位词

方法一：定长滑窗

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
          //保存答案
        List<Integer> res = new ArrayList<>();

        //p的异位词
        //给定两个字符串 s 和 p，找到 s 中所有 p 的
        //异位词
        // 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
        int[] cntS = new int[30];
        int[] cntP = new int[30];
        //取出子串
        for (char c : p.toCharArray()) {
              cntP[c-'a']++;
        }
        for(int r=0;r<s.length();r++)
        {
            cntS[s.charAt(r)-'a']++;
            int l = r - p.length() + 1;
            if(l<0){
                continue;
            }
            if(Arrays.equals(cntS,cntP)){
                res.add(l);
            }
            cntS[s.charAt(l) - 'a']--;
        }

        return res;
    }
}

方法二：不定长滑窗

class Solution {
    public List<Integer> findAnagrams(String s, String p) { List<Integer> res = new ArrayList<>();
        int[] cnt = new int[30];

        for (char c : p.toCharArray()) {
            cnt[c-'a']++;
        }
        int l=0;
        for(int r=0;r<s.length();r++)
        {
            int c = s.charAt(r)-'a';
            cnt[c]--;
           while(cnt[c]<0) {  
            cnt[s.charAt(l)-'a']++;
            l++;
           }
            if(r-l+1==p.length())
            {
                res.add(l);
            }

        }
        
        return res;
    }
}