438. Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

第一次做这种题，想了很久都没有想出这种方法，用其它方法做的时候，时间又超了。

Sliding Window：大体思路就是用一个窗划过字符串s。窗内初始时装载目标字符串，窗划过字符串s，减去进入窗的字符，加上离开窗的字符。若窗内的字符数为0，则表明目标字符串依次进入了窗。

public class Solution {

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if(p.length() > s.length())
            return res;
        char[] sStr = s.toCharArray();
        int[]map = new int[26];
        for(char ch:p.toCharArray())
            map[ch - 'a']++;
        int j = 0;
        for(j=0; j<p.length()-1; j++)           //窗只出不进
            map[sStr[j] - 'a']--;
        for(int i=0; j<s.length(); i++, j++){
            map[sStr[j] - 'a']--;
            if(check(map))
                res.add(i);
            map[sStr[i] - 'a']++;
        }
        return res;
    }
    public boolean check(int[]map){
        for(int n:map)
            if(n > 0)   return false;
        return true;
    }
}