题目

给定两个字符串 s 和 p，找到 s 中所有 p 的 

异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

解答

解法一 滑动窗口+ 字符串排序

滑动窗口大小为p的长度

用窗口里的字符重排序后得到的字符串和排序过的p相比较，如果一致就把左指针放入result数组。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (s.length() < p.length() && s.equals(p))
            return null; 
        // p的长度为滑动窗口的大小
        int left = 0, right = p.length() - 1;
        char[] char_s = s.toCharArray();
        char[] char_p = p.toCharArray();
        Arrays.sort(char_p);
        p = new String(char_p);
        List<Integer> result = new ArrayList<>();
        while (right < s.length()) {
            char[] chars = new char[p.length()];
            for (int i = 0; i < p.length(); i++) 
                chars[i] = char_s[i+left];
            Arrays.sort(chars);
            String word = new String(chars);
            if (word.equals(p)) result.add(left);
            left++;
            right++;
        }
        return result;
    }
}

自信满满提交，结果O(N²)。

优化 – 如果右指针指向的字符在HashSet_p中没有，就直接移动窗口

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (s.length() < p.length() && s.equals(p))
            return null; 
        // p的长度为滑动窗口的大小
        int left = 0, right = p.length() - 1;
        char[] char_s = s.toCharArray();
        char[] char_p = p.toCharArray();
        Set<Character> set_p = new HashSet<Character>();
        for (char c : char_p) set_p.add(c);
        Arrays.sort(char_p);
        String word = String.valueOf(chars);
        List<Integer> result = new ArrayList<>();
        while (right < s.length()) {
            if (!set_p.contains(char_s[right])){
                for (int i = 0; i < p.length(); i++) {
                    left++;
                    right++; 
                }
                continue;
            } 
            char[] chars = new char[p.length()];
            for (int i = 0; i < p.length(); i++) 
                chars[i] = char_s[i+left];
            Arrays.sort(chars);
            String word = String.valueOf(chars);
            if (word.equals(p)) result.add(left);
            left++;
            right++;
        }
        return result;
    }
}

有提升，但不多

解法二 用频率数组记录窗口中字符出现的次数

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length() && !s.equals(p))
            return result;
        // p的长度为滑动窗口的大小
        int left = 0, right = p.length() - 1;
        char[] char_s = s.toCharArray();
        char[] char_p = p.toCharArray();
        int[] counts = new int[26];
        // 得到字符频率数组
        for (char c : char_p) counts[c - 'a']++;
        while (right < s.length()) {
            int[] currentCounts = new int[26];
            for (int i = 0; i < p.length(); i++) 
                currentCounts[char_s[i+left] - 'a']++;
            if (Arrays.equals(currentCounts, counts)) result.add(left);
            left++;
            right++;
        }
        return result;
    }
}

优化 – 滑动窗口的精髓

不是每次滑动窗口都重新计算窗口中的频率，而是应该每次滑动时更新窗口边界的字符频率。

这样可以将时间复杂度从O(N*M)优化到O(N)!

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length() && !s.equals(p))
            return result;
        // p的长度为滑动窗口的大小
        int left = 0, right = p.length() - 1;
        char[] char_s = s.toCharArray();
        char[] char_p = p.toCharArray();
        int[] counts = new int[26];
        // 得到字符频率数组
        for (char c : char_p) counts[c - 'a']++;
        int[] currentCounts = new int[26];
        for (int i = 0; i < p.length(); i++) 
            currentCounts[char_s[i] - 'a']++;
        if (Arrays.equals(currentCounts, counts)) result.add(left);
        left++;
        right++;
        while (right < s.length()) {
            currentCounts[char_s[left-1] - 'a']--;
            currentCounts[char_s[right] - 'a']++;
            if (Arrays.equals(currentCounts, counts)) result.add(left);
            left++;
            right++;
        }
        return result;
    }
}

win!!!

直观思路优化

每新加入一个元素入窗口，判断这个元素是不是p要求的字母

• 如果不是，将左指针和右指针都指向当前右指针后一个元素，因为前面不可能有要找的子串
• 否则，判断加入这个字符会不会让这个字母的计数大于要求
  • 如果会，移动左指针直到回到要求范围
  • 否则正常移动右指针。

这个思路和 昨天的 无重复字符的最长子串 很相似。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int left = 0, right = 0;
        
        int[] cnt_p = new int[26], cnt_window = new int[26];
        char[] chars_s = s.toCharArray(), chars_p = p.toCharArray();
        for (char c : chars_p) cnt_p[c - 'a']++;

        while (right < chars_s.length) {
            // 新加入字符的是子串中的
            if (cnt_p[chars_s[right] - 'a'] != 0) {
                if(++cnt_window[chars_s[right] - 'a'] > cnt_p[chars_s[right] - 'a']) {
                    while (cnt_window[chars_s[right] - 'a'] > cnt_p[chars_s[right] - 'a']) {
                        cnt_window[chars_s[left++] - 'a']--;
                    }
                }
                if (Arrays.equals(cnt_p, cnt_window)) {
                    // 找到子串    
                    result.add(left);
                    cnt_window[chars_s[left++] - 'a']--;
                }
                // 还没找到子串
                 right++;
            } else {
                left = right + 1;
                right++;
                Arrays.fill(cnt_window, 0);
            }
        }
        return result;
    }
}

小结

滑动窗口的一个关键解题思路：如果右指针新加入的元素使得该元素计数大于要求，就右移左指针缩小窗口直到重新符合要求。 – 无重复字符的最长子串 找到字符串中所有字母异位词 两题都是这个思想。

活动窗口的精髓在于只需要关注窗口边界的变化，而不需要重新计算整个窗口的内容。
比如本题对窗口内字符频率数组的维护，不是每次移动窗口都重新计算这个频率数组，而是动态维护。

下面是chatGPT对滑动窗口的思想总结

滑动窗口的核心思想可以总结为以下几点：

1. 窗口逐步移动而不是重置：

• 传统方法通常会遍历所有可能的子数组或子串，导致大量的重复计算。而滑动窗口通过在当前子数组/子串的基础上增删元素来避免重新计算整个窗口的内容。例如，从数组中移除最左边的元素并添加最右边的元素，窗口大小不变，但位置移动。

2. 高效处理连续子区间问题：

• 滑动窗口特别适合处理子数组或子串等连续区间问题，比如寻找子数组和、字符串中的子串匹配问题。它让算法的时间复杂度从 O(n²) 降低到 O(n)，因为每次窗口的移动都只涉及少量的更新操作。

3. 动态维护窗口内的信息：

• 在窗口移动的过程中，动态维护窗口内的统计信息，比如字符的频率、窗口内元素的和、最大/最小值等。窗口每次只更新边界上的元素，而不需要重新计算整个窗口的内容。