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

题意: 给定一个字符串和一个target字符串，找出字符串中target字符串的所有字母的同素异形体的位置

思路：用map记录target字符串中字符出现的个数，然后维护滑动窗口遍历字符串，具体见代码

思想：滑动窗口

复杂度：时间O（n)，空间O(n)

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList();
        int[] map = new int[26];
        int len = p.length();
        // p比s长，返回空
        if(s.length() < len)
            return res;
        // 创建字典字符串
        for(int i=0;i<len;i++) {
            int cur = p.charAt(i) - 'a';
            map[cur]++;
        }
        
        int start = 0;
        int end = 0;
        // temp字典用来记录当前已经匹配的窗口
        int[] temp = new int[26];
        while(end < s.length()) {
            int cur = s.charAt(end) - 'a';
            // 字符串合法则不断移动end指针
            while(map[cur] > temp[cur]) {
                temp[cur]++;
                end++;
                if(end < s.length())
                    cur = s.charAt(end) - 'a';
            }
            // 找到一个合法的字符串
            if(end - start == len) {
                res.add(start);
            }
            // 最后一个不匹配的字符在p中出现过，只前移start指针
            if(map[cur] > 0) {
                int head = s.charAt(start++) - 'a';
                temp[head]--;
            } else {
                // 最后一个不匹配的字符在品种没出现过，重置窗口，并移动end，把start设为end
                temp = new int[26];
                end++;
                start = end; 
            }
        }
        return res;
    }
}