438 找到异位字符串

思路：

这道题我是暴力了，但是我知道应该用滑动窗口。因为很明显，当需要判断[i + 1, j + 1]的字符是否为异位字符时，我们可以利用[i, j]的信息，但是这里我不知道怎么办。

正确的思路是维护一个滑动窗口，如果当前窗口内的右指针指向的字符数量大于对应字符的数量，那么就不断地缩小窗口，直到小于等于位置（应该等于就停下来了）。如果此时窗口大小等于异位字符长度，那么就是一个正确的位置

代码：

class Solution {
    public List findAnagrams(String s, String p) {
        int n = s.length(), m = p.length();
        List res = new ArrayList<>();
        if(n < m) return res;

        int[] pCnt = new int[26];
        int[] sCnt = new int[26];

        for(int i = 0; i < m; i++){
            pCnt[p.charAt(i) - 'a'] ++;
        }

        int left = 0;
        for(int right = 0; right < n; right++){
            int curRight = s.charAt(right) - 'a';
            sCnt[curRight]++;
            while(sCnt[curRight] > pCnt[curRight]){
                int curLeft = s.charAt(left) - 'a';
                sCnt[curLeft]--;
                left++;
            }
            if(right - left + 1 == m){
                res.add(left);
            }
        }
        return res;
    }
}

作者：edelweisskoko
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/438-zhao-dao-zi-fu-chuan-zhong-suo-you-z-nx6b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。