【LeetCode】Day147-找到字符串中所有字母异位词

题目

438. 找到字符串中所有字母异位词【中等】

题解

自己ac的一道滑动窗口题！虽然花了挺久代码也比较复杂，但还是很开心！主要参照的是76题 最小覆盖子串【困难】，这两题的不同点是本题需要 s子串和 t 完全相同，而76则需要 s 覆盖 t 。

滑动窗口

思路
（虽然用76题的思路也可以做，但是把困难题的方法套在中等题上毕竟做复杂了，所以还是需要具体问题具体分析

由于p的异位词长度和p的长度一定相同，所以在字符串s中构造一个长度和p相等的滑动窗口，并在滑动中维护窗口中每种字符的数量；如果滑动窗口中每种字母数量和p中相同，则说明当前窗口内字符串为p的异位词。

class Solution {
    int[] pmap=new int[26];
    int[] smap=new int[26];
    public List<Integer> findAnagrams(String s, String p) {
        int n=s.length(),m=p.length();
        List<Integer>res=new ArrayList<>();
        if(n<m)
            return res;
        //初始化滑动窗口
        for(int i=0;i<m;i++){
            pmap[p.charAt(i)-'a']++;
            smap[s.charAt(i)-'a']++;
        }
        if(Arrays.equals(smap,pmap))
            res.add(0);
        //滑动窗口
        for(int i=0;i<n-m;i++){
            //向前滑动一位
            smap[s.charAt(i)-'a']--;
            smap[s.charAt(i+m)-'a']++;

            if(Arrays.equals(smap,pmap))
                res.add(i+1);
        }
        return res;
    }
}

时间复杂度：$O(m+(n-m)\ast 26)$

空间复杂度：$O(26)$

改进的滑动窗口

不再分别统计滑动窗口和 p 内每种字母的数量，而是引入变量 diff 记录窗口内与p中数量不同的字母的个数。
判断窗口内是否是p的异位词，只需要判断diff是否为0即可。

count数组的含义：[0:25]，数组下标表示字母，数组值是s和p的字母差值。
初始化：确定起点为0时，s和p的字母差值，保存在count数组中，即遍历滑窗，s有字母*，对应count[*]++，p有字母#，对应count[#]–
count[i]可能的取值：
（1）== 1，表示s有这个字母，p没有
（2）== 0，表示s有，p也有；或者s没有，p没有
（3）== -1，表示s没有，p有
 
窗口滑动过程中，

1. s[i]处的字母要被滑走了，此时如果（1）count[s[i]处的字母]==1，所以之前s有，p没有，现在s没有了，diff–（2）count[s[i]处的字母]==0，已经确定s有了，所以p也会有，现在s没有了，所以diff++
2. s[plen+i]处的字母要滑进来了，如果（1）count[s[plen+i]处的字母]==-1，所以之前s没有，p有，现在s有了，diff–（2）count[s[plen+i]处的字母]==0，已经确定s会有了，所以比p多一个，所以diff++

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int n=s.length(),m=p.length();
        List<Integer>res=new ArrayList<>();
        if(n<m)
            return res;
        //初始化滑动窗口
        int[] count=new int[26];
        for(int i=0;i<m;i++){
            count[s.charAt(i)-'a']++;
            count[p.charAt(i)-'a']--;
        }
        int diff=0;
        for(int i=0;i<26;i++){
            if(count[i]!=0)
                diff++;
        }
        if(diff==0)
            res.add(0);

        //滑动窗口
        for(int i=0;i<n-m;i++){
            /*s[i]滑走了以后*/
            int c1=count[s.charAt(i)-'a'];
            if(c1==1)
                diff--;//s[i]滑走了以后,c1会变成0,因此不同的字母数量-1
            else if(c1==0)
                diff++;//s[i]滑走了以后,c1会变成-1,因此不同的字母数量+1
            count[s.charAt(i)-'a']--;
            
            /*s[i+m]滑进来以后*/
            int c2=count[s.charAt(i+m)-'a'];
            if(c2==-1)
                diff--;
            else if(c2==0)
                diff++;
            count[s.charAt(i+m)-'a']++;

            if(diff==0)
                res.add(i+1);
        }
        return res;
    }
}

时间复杂度：$O(m+n+26)$，我们需要 O(m) 来统计字符串 p 中每种字母的数量；需要 O(m) 来初始化滑动窗口；需要 O(Σ) 来初始化 differ；需要 O(n−m) 来滑动窗口并判断窗口内每种字母的数量是否与字符串 p 中每种字母的数量相同，每次判断需要O(1)。

空间复杂度：$O(26)$