滑动窗口算法

滑动窗口算法可以应用在很多查找字符串子串的算法中。

参考：Sliding Window algorithm template to solve all the Leetcode substring search problem.

---

算法1: 基本滑动窗口算法

使用HashMap存储target字符串中字符出现的次数，适用范围最广。

public List<Integer> slidingWindowTemplate(String s, String t) {
    //初始化一个集合用来存储结果
    List<Integer> result = new LinkedList<>();
    if(t.length()> s.length()) return result;

    //创建一个HashMap用来存储目标子串中字符的出现次数
    Map<Character, Integer> map = new HashMap<>();
    for(char c : t.toCharArray()){
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    //维护一个counter检查是否和目标串匹配
    //这里是map.size()而不是t.size()所以下面counter--的时候判断条件是map.get(c)==0
    //如果这里是t.length()由于可能存在重复数字，若以下面counter--的时候判断条件应该是map.get(c)>0 
    int counter = map.size();

    //两个指针：begin:滑窗的左指针，end:滑窗的右指针
    int begin = 0, end = 0;

    while(end < s.length()){
        char c = s.charAt(end);
        if( map.containsKey(c) ){
            map.put(c, map.get(c)-1);
            if(map.get(c) == 0) counter--;
        }
        end++;
        
        while(counter == 0){
            char tempc = s.charAt(begin);
            if(map.containsKey(tempc)){
                map.put(tempc, map.get(tempc) + 1);
                if(map.get(tempc) > 0) counter++;
            }
            begin++;
        }
    }
    return result;
}

如果一直target中字符的取值范围，如target中只包含大写字母、小写字母或数字，则该算法可以进一步优化，主要的优化点就是将HashMap换成数组，对数组的操作要比对HashMap的entry操作快很多。

算法2: 使用数组作为map的滑动窗口算法

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    int[] map = new int[256];
    for (char c : p.toCharArray())
        map[c]++;

    int count = p.length();
    int start = 0;
    for (int end = 0; end < s.length(); end++) {
        if (map[s.charAt(end)]-- > 0){
            count--;
        }

        while (count == 0) {
            //if (end - start + 1 == p.length())
                //res.add(start);
            if (++map[s.charAt(start)] > 0)
                count++;
            start++;
        }
    }
    return res;
}