438. 找到字符串中所有字母异位词--滑动窗口

438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
//初始化窗口
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }
//判断初始化窗口是否为 异位词
        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }
//开始滑动s上的窗口，判断是否为异位词
        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];

            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}
复杂度分析

时间复杂度：O(m+(n−m)×Σ)，其中 n 为字符串 s 的长度，m 为字符串 p 的长度，Σ 为所有可能的字符数。我们需要 O(m) 来统计字符串 p 中每种字母的数量；需要 O(m) 来初始化滑动窗口；需要判断 n−m+1 个滑动窗口中每种字母的数量是否与字符串 p 中每种字母的数量相同，每次判断需要 O(Σ) 。因为 s 和 p 仅包含小写字母，所以 Σ=26。

空间复杂度：O(Σ)。用于存储字符串 p 和滑动窗口中每种字母的数量。

方法二 优化的滑动窗口

differ 来记录当前窗口与字符串 p 中数量不同的字母的个数
滑动窗口
s:source p:target

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] count = new int[26];
1. 初始化滑动窗口
        for (int i = 0; i < pLen; ++i) {
            ++count[s.charAt(i) - 'a'];
            --count[p.charAt(i) - 'a'];
        }
2. 初始化滑动窗口的differ
        int differ = 0;
        for (int j = 0; j < 26; ++j) {
            if (count[j] != 0) {
                ++differ;
            }
        }
3. 判断初始化的滑动窗口是否存在异位词
        if (differ == 0) {
            ans.add(0);
        }
4. 开始向右滑动，并进行比较
        for (int i = 0; i < sLen - pLen; ++i) {
5. 窗口左边界，之前为1，表示s中比p多1，不同，现在窗口收缩减去，等于0，则differ-1；
              之前为0表示相同，现在窗口收缩减去1，等于-1，则differ+1；
                  --》窗口左边界收缩
            if (count[s.charAt(i) - 'a'] == 1) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i) - 'a'] == 0) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            --count[s.charAt(i) - 'a'];
6. 窗口右边界，动态更新differ
          之前为-1，窗口向右滑动，加1，则等于0，即differ-1
          之前为0，现在如果窗口向右滑动，加1，则等于1，即differ+1
                ==》窗口右边界向右滑动
（判断窗口内每种字母的数量是否与字符串 p 中每种字母的数量相同）
            if (count[s.charAt(i + pLen) - 'a'] == -1) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
                --differ;
            } else if (count[s.charAt(i + pLen) - 'a'] == 0) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
                ++differ;
            }
            ++count[s.charAt(i + pLen) - 'a'];
            
            if (differ == 0) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}
时间复杂度：O(n+m+Σ)，其中 n 为字符串 s 的长度，m 为字符串 p 的长度，其中Σ 为所有可能的字符数。我们需要 O(m) 来统计字符串 p 中每种字母的数量；需要 O(m) 来初始化滑动窗口；需要 O(Σ) 来初始化 differ；需要 O(n−m) 来滑动窗口并判断窗口内每种字母的数量是否与字符串 p 中每种字母的数量相同，每次判断需要 O(1) 。因为 s 和 p 仅包含小写字母，所以 Σ=26。

空间复杂度：O(Σ)。用于存储滑动窗口和字符串 p 中每种字母数量的差