从零学 Java 滑动窗口：「找到字符串中所有字母异位词」的思路拆解

问题定义

给定字符串 s 和 p，需在 s 中找到所有 p 的字母异位词（即字母相同但顺序不同的子串），返回起始索引。
示例：
$s = \text{"cbaebabacd"},\ p = \text{"abc"}$
输出：$[0,6]$（子串 $\text{"cba"}$ 和 $\text{"bac"}$）

---

暴力解法缺陷

直接遍历所有长度为 $|p|$ 的子串，检查是否与 $p$ 为异位词：

for (int i = 0; i <= s.length() - p.length(); i++) {
    String sub = s.substring(i, i + p.length());
    if (isAnagram(sub, p)) results.add(i); // 需排序或哈希比较
}

问题：时间复杂度 $O(n \times m \log m)$（$n=|s|, m=|p|$），当 $n$ 较大时效率低。

---

滑动窗口优化

核心思想：利用双指针动态维护窗口，通过频率数组避免重复计算。
步骤拆解：

1. 初始化频率数组
   用长度 26 的数组 pCount 和 winCount 分别记录 $p$ 和当前窗口的字母频率：
   $$ \text{pCount}[i] = p\text{ 中第 }i\text{ 个字母出现次数} $$
   （$i$ 对应 char - 'a'）

2. 双指针滑动窗口

   • 右指针 right：逐字符右移，更新 winCount
   • 左指针 left：当窗口长度 $= |p|$ 时，检查是否匹配，然后左移

3. 高效匹配检查

   • 维护变量 match 记录当前匹配的字母数量
   • 当 winCount 中某字母频率 $=$ pCount 时，match++
   • 若 match == 26，则找到异位词，记录 left

4. 窗口收缩
   左移 left 前，减少 winCount 中对应字母频率，并更新 match。

---

完整代码实现

import java.util.*;

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s.length() < p.length()) return result;
        
        int[] pCount = new int[26];
        int[] winCount = new int[26];
        
        // 初始化 p 的频率数组
        for (char c : p.toCharArray()) {
            pCount[c - 'a']++;
        }
        
        int left = 0, right = 0, match = 0;
        while (right < s.length()) {
            char rChar = s.charAt(right);
            winCount[rChar - 'a']++;
            
            // 更新匹配状态：当前字母频率不超过 p 时才算有效匹配
            if (winCount[rChar - 'a'] <= pCount[rChar - 'a']) {
                match++;
            }
            right++;
            
            // 窗口长度 = p.length() 时开始检查
            if (right - left == p.length()) {
                if (match == p.length()) { // 所有字母均匹配
                    result.add(left);
                }
                
                char lChar = s.charAt(left);
                // 左移前更新状态
                if (winCount[lChar - 'a'] <= pCount[lChar - 'a']) {
                    match--;
                }
                winCount[lChar - 'a']--;
                left++;
            }
        }
        return result;
    }
}

---

复杂度分析

• 时间复杂度：$O(n)$，$n$ 为 s 的长度，双指针各遍历一次
• 空间复杂度：$O(1)$，固定长度频率数组

关键点：

1. 用 match 避免每次全量比较数组
2. 窗口滑动时同步更新频率和匹配状态
3. 右指针扩展窗口，左指针仅在窗口达标后收缩

提示：可通过打印 winCount 和 match 的值，逐步验证窗口移动过程，加深理解！