14.【滑动窗口】

14.【滑动窗口】

新建两个哈希表（数组模拟） ：通过比较两个哈希表是否一样用来判断是否是异位词 hashS用来统计字符串s的字符出现次数， hashP用来统计字符串p的字符出现次数， 通过滑动窗口 每当right - left + 1 > 字符串p的长度的时候。此时令 left++并让left-‘a’指向的字符出现次数-- 来保证这个窗口大小是 <= 字符串p的长度 每当窗口大小等于字符串p的长度，就比较两个hash数组是否一样。若一样，就添加left下标 到ret顺序表中

class Solution {
    public List<Integer> findAnagrams(String s0, String p0) {
        int[] hashS = new int[26]; //通过比较两个哈希表是否一样用来判断是否是异位词
        int[] hashP = new int[26];
        char[] s = ();//字符串转数组，方便求解
        char[] p = ();
        int m = s0.length(),n = p0.length(); //得到两字符串长度
        List<Integer> ret = new ArrayList<>();

        for (int i = 0; i < n; i++) {   //将p字符串扔进拟哈希表p。等待与拟哈希表s进行比较
            hashP[p[i] - 'a']++;
        }
        for (int left = 0,right = 0; right < m; right++) {
            hashS[s[right] - 'a']++;    //进窗口
            if(right - left + 1 > n){   //如果进多了，那么就出窗口。
                hashS[s[left++]-'a']--;
            }
            if ((hashS, hashP)){ //此时窗口大小一定为p数组长度的大小。
                ret.add(left); //比较两哈希表是否一致，如果一致，就添加初始索引。
            }
        }
        return ret; //最终返回初始索引数组集
    }
}

后面自己写出来的

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] hashS = new int[26];
        int[] hashP = new int[26];
        List<Integer> ret = new ArrayList<>();
        int m = s.length(),n = p.length();

        for(int i = 0; i < n; i++){
            hashP[(i)-'a']++;
        }

        for(int left = 0,right = 0; right < m; right++){
            hashS[(right) - 'a']++;
            if(right - left + 1 > n){
                hashS[(left++) - 'a']--;
            }
            if((hashS,hashP)){
                ret.add(left);
            }
        }
        return ret;
    }
}

再小小优化一下

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int[] hashS = new int[26];
        int[] hashP = new int[26];
        List<Integer> ret = new ArrayList<>();
        int m = s.length(),n = p.length();

        for(int i = 0; i < n; i++){
            hashP[(i)-'a']++;
        }

        for(int left = 0,right = 0; right < m; right++){
            hashS[(right) - 'a']++;
            if(right - left + 1 > n){
                hashS[(left++) - 'a']--;
            }if(right - left + 1 == n && (hashS,hashP)){
                ret.add(left);
            }
        }
        return ret;
    }
}

时间复杂度：O（m+n） m和n分别是字符串s和p的长度 空间复杂度：O（m） m是字符串s的长度