leetcode刷题（91）——438. 找到字符串中所有字母异位词

输入:
s: "cbaebabacd" p: "abc"

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

输入:
s: "abab" p: "ab"

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        ArrayList<Integer> result = new ArrayList();

        int[] target = new int[26];
        int[] window = new int[26];
        int targetSize = 0;
        for (int i = 0; i < p.length(); i++) {
            char ch = p.charAt(i);
            target[ch - 'a']++;
            //记录target数组中有值的size
            if (target[ch - 'a'] == 1) {
                targetSize++;
            }
        }
        int left = 0;
        int right = 0;
        int valid = 0;
        while (right < s.length()) {
            char ch = s.charAt(right);
            right++;
            if (target[ch - 'a'] != 0) {
                window[ch - 'a']++;
                if (target[ch - 'a'] == window[ch - 'a']) {
                    valid++;
                }
            }
            while (right - left == p.length()) {
                // 在这里判断是否找到了合法的子串
                if (valid == targetSize)
                    result.add(left);
                char d = s.charAt(left);
                left++;
                if (target[d - 'a'] != 0) {
                    if (target[d - 'a'] == window[d - 'a']) {
                        valid--;
                    }
                    window[d - 'a']--;
                }
            }
        }
        return result;
    }
}