findAnagrams(滑动窗口)

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".

Anagrams的意思是(字符都有，顺序可以不同的字符串，也可以说是异序)。
这道题就是根据p在s中找有多少个Anagrams，返回一个数组。
这道题的解题思路就是利用滑动窗口算法。

1.将p转换进入一个hash表，value记录每一个key的出现次数。
2.初始化两个指针left,right，两个指针构成一个窗口。
3.初始化一个different(差异度),类型为int,长度为p.length，差异度代表了窗口内的字符串与p有多大差别，当different==0的时候代表该窗口内的字符串和p为Anagrams。
4.窗口进行滑动，当right右移，判断s[right]是否在hash表内，若在则hash表-1，different-1。当left右移，判断s[left-1]是否在hash表内，若在则hash表+1，different+1。
5.每次滑动判断different差异度是否0，若为0则遍历hash表，查看是否所有的value均为0(这步很重要，具体为什么要这样，自己敲一边就明白了)

代码如下，时间复杂度为O(n)，总结起来就是题不难，难点是思路，在不知道滑动窗口算法之前，简直想到爆炸

package com.example.demo.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @description:
 * @author: 王泽龙
 * @create: 2019-05-07 15:37
 **/
public class findAnagrams {
    public static List<Integer> findAnagrams(String s, String p) {
        char[] cp = p.toCharArray();
        Map<Character, Integer> mp = new HashMap<>();
        for(int i=0;i<cp.length;i++){
            if(mp.containsKey(cp[i]))mp.put(cp[i],mp.get(cp[i])+1);
            else mp.put(cp[i],1);
        }
        char[] cs = s.toCharArray();
        int different = p.length();
        List<Integer> res = new ArrayList<>();
        int l=0,r=0;
        while(r<s.length()){
            if(r-l<=p.length()){
                if(mp.containsKey(cs[r])){
                    different--;
                    mp.put(cs[r],mp.get(cs[r])-1);
                }
                r++;
            }
            if(r-l>p.length()){
                l++;
                if(mp.containsKey(cs[l-1])){
                    different++;
                    mp.put(cs[l-1],mp.get(cs[l-1])+1);
                }
            }
            if(different==0){
                boolean flag = true;
                for(Map.Entry<Character, Integer> e: mp.entrySet()){
                    if(e.getValue()!=0){
                        flag=false;
                        break;
                    }
                }
                if(!flag)continue;
                res.add(l);
            }
        }
        return res;
    }
}