三、滑动窗口——9. 找到字符串中所有字母异位词

滑动窗口的核心要点：

1. 维护一个有条件的滑动窗口
2. 右端点右移，导致窗口扩大，是不满足条件的罪魁祸首
3. 左端点右移目的是为了缩小窗口，重新满足条件

题目描述

给定两个字符串 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. 统计目标字符频率
   使用数组 cnt 统计字符串 p 中每个字符的出现次数。例如，若 p=“aab”，则 cnt[‘a’-‘a’]=2，cnt[‘b’-‘a’]=1。
2. 滑动窗口遍历字符串 s
   维护窗口的左右指针 left 和 right，初始时 left=0。右指针 right 逐个遍历字符，将当前字符加入窗口（对应计数减1）。
3. 动态调整窗口左边界
   若当前字符的计数变为负数，说明窗口中该字符的数量超过 p 中的要求（或字符不在 p 中），需移动左指针 left，恢复被移出窗口的字符计数，直到该字符的计数不再为负。
4. 记录有效窗口
   当窗口长度等于 p 的长度时，说明窗口内字符的频率与 p 完全匹配，此时将左指针 left 加入结果列表。

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
            List<Integer> ans = new ArrayList<>();
            int[] cnt = new int[26];
            for (char c : p.toCharArray()) {
                cnt[c-'a']++;
            }
            int left = 0;
            for (int right = 0; right < s.length(); right++) {
                int c = s.charAt(right)-'a';
                cnt[c]--;
                while (cnt[c] < 0){
                    cnt[s.charAt(left) - 'a']++;
                    left++;
                }
                if (right - left +1 == p.length()){
                    ans.add(left);
                }
            }
            return ans;
        }
}