找到字符串中所有字母异位词：滑动窗口收集所有结果
找到字符串中所有字母异位词：滑动窗口收集所有结果
适读人群：Java 后端工程师、算法中阶学习者 | 阅读时长：约 15 分钟 | 难度：⭐⭐⭐
开篇故事
LeetCode 438 和上一篇的 567 几乎是同一道题，区别只是返回所有匹配位置，而不只是判断是否存在。
我把这两道题放在一起，是为了强调一个学习方法：很多算法题之间有细微的变化关系，掌握一道题的核心框架后，通过局部修改就能解决一系列变体题目。这种"题目变体意识"是刷题效率的关键。
这篇文章的另一个重点，是展示如何从"找第一个"到"找所有"的代码改造过程，以及如何保持代码结构清晰。
一、题目解析
题目（LeetCode 438）： 给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
示例：
s = "cbaebabacd"，p = "abc"，输出：[0, 6]s = "abab"，p = "ab"，输出：[0, 1, 2]
二、解法一：暴力 O(n * m log m)
public class Solution1 {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (p.length() > s.length()) return result;
char[] sortedP = p.toCharArray();
Arrays.sort(sortedP);
int m = p.length();
for (int i = 0; i <= s.length() - m; i++) {
char[] window = s.substring(i, i + m).toCharArray();
Arrays.sort(window);
if (Arrays.equals(window, sortedP)) {
result.add(i);
}
}
return result;
}
}复杂度分析
- 时间复杂度：O(n * m log m)。
- 空间复杂度：O(m)。
三、解法二：固定窗口 + 频次数组比较
public class Solution2 {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (p.length() > s.length()) return result;
int m = p.length(), n = s.length();
int[] freqP = new int[26];
int[] freqW = new int[26];
for (char c : p.toCharArray()) freqP[c - 'a']++;
for (int i = 0; i < m; i++) freqW[s.charAt(i) - 'a']++;
if (Arrays.equals(freqP, freqW)) result.add(0);
for (int right = m; right < n; right++) {
freqW[s.charAt(right) - 'a']++;
freqW[s.charAt(right - m) - 'a']--;
if (Arrays.equals(freqP, freqW)) result.add(right - m + 1);
}
return result;
}
}复杂度分析
- 时间复杂度：O(26n)，即 O(n)。
- 空间复杂度：O(1)。
四、解法三最优：diff 计数器，O(1) 每步
Mermaid 图
完整代码
public class Solution3 {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (p.length() > s.length()) return result;
int m = p.length(), n = s.length();
int[] freq = new int[26]; // freq = freqP - freqW（窗口）
// 初始化 freq（s1 正，s2 负）
for (char c : p.toCharArray()) freq[c - 'a']++;
for (int i = 0; i < m; i++) freq[s.charAt(i) - 'a']--;
// 计算初始 diff
int diff = 0;
for (int f : freq) if (f != 0) diff++;
if (diff == 0) result.add(0);
// 滑动窗口
for (int right = m; right < n; right++) {
int rightChar = s.charAt(right) - 'a';
int leftChar = s.charAt(right - m) - 'a';
// 纳入 right 处字符（减少 freq，因为 freq = freqP - freqW）
freq[rightChar]--;
if (freq[rightChar] == 0) diff--;
else if (freq[rightChar] == -1) diff++;
// 移出 left 处字符（增加 freq）
freq[leftChar]++;
if (freq[leftChar] == 0) diff--;
else if (freq[leftChar] == 1) diff++;
// 记录满足条件的起始位置
if (diff == 0) result.add(right - m + 1);
}
return result;
}
public static void main(String[] args) {
Solution3 sol = new Solution3();
System.out.println(sol.findAnagrams("cbaebabacd", "abc")); // [0, 6]
System.out.println(sol.findAnagrams("abab", "ab")); // [0, 1, 2]
System.out.println(sol.findAnagrams("baa", "aa")); // [1]
System.out.println(sol.findAnagrams("aa", "bb")); // []
}
}复杂度分析
- 时间复杂度：O(n + m)。初始化 O(m)，滑动 O(n)，每步 O(1)。
- 空间复杂度：O(1)。
五、举一反三
567 -> 438 的改造规律：
| 改动点 | LeetCode 567 | LeetCode 438 |
|---|---|---|
| 返回类型 | boolean | List<Integer> |
| 找到匹配时 | return true | result.add(startIdx) |
| 函数结尾 | return false | return result |
代码核心框架完全相同，只改三处。
六、踩坑实录
坑一：起始索引计算错误
当 right 指向当前窗口的最后一个字符时，窗口起始索引是 right - m + 1，不是 right - m。一个常见的验证方法：当 right = m-1（第一个完整窗口的最后位置）时，起始应该是 0，代入 right - m + 1 = m - 1 - m + 1 = 0，正确。
坑二：diff 初始值的计算
初始化完第一个窗口的 freq 后，需要正确计算 diff（不等于 0 的字符数）。不能直接设 diff = 0 或 diff = 26，要实际遍历 freq 数组统计。
坑三：把 567 的 return true 直接改成了 return，但没有改函数签名
如果复用 567 的代码框架，要注意改的不只是返回语句，还有返回值类型和参数名。代码复用时不要改了一半忘了另一半。
七、总结
LeetCode 438 是 567 的"收集所有结果"版本，代码框架几乎完全一样，核心差异只是：找到匹配时不立即返回，而是记录起始位置后继续滑动。
这种"找一个 vs 找所有"的模式在滑动窗口问题里非常普遍，掌握了这对孪生题目，你就建立了一种"变体迁移"的解题能力。
下一篇的滑动窗口最大值（239）会引入单调队列，把滑动窗口的能力进一步提升，从字符频次扩展到区间极值维护。