这是一道经典的 滑动窗口 + 哈希表 问题。
📌 题目描述
给定两个字符串 s 和 p，找出 s 中所有 p 的字母异位词 的起始索引。
- 字母异位词：由相同字符、不同顺序组成的字符串（如
"abc"和"bca"） - 返回所有起始下标（升序）
✅ 解题思路：滑动窗口 + 字符频次统计
由于异位词的 字符种类和数量完全一致，我们可以：
- 统计
p中每个字符的频次（目标频次） - 在
s上维护一个 长度为p.length()的滑动窗口 - 每次窗口滑动时，更新窗口内字符频次
- 若窗口频次与
p频次一致 → 找到一个异位词，记录起始索引
为高效实现，我们使用 固定大小的滑动窗口，并用数组（或哈希表）记录频次。
💡 Java 实现（方法一：双频次数组）
适用于只含小写字母的情况（题目保证）：
import java.util.*;
public class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) return result;
// 频次数组（26个小写字母）
int[] pCount = new int[26];
int[] windowCount = new int[26];
// 初始化 p 的频次
for (char c : p.toCharArray()) {
pCount[c - 'a']++;
}
// 初始化第一个窗口 [0, pLen - 1]
for (int i = 0; i < pLen; i++) {
windowCount[s.charAt(i) - 'a']++;
}
// 检查第一个窗口
if (Arrays.equals(pCount, windowCount)) {
result.add(0);
}
// 滑动窗口：从 i = pLen 开始，每次加入 s[i]，移除 s[i - pLen]
for (int i = pLen; i < sLen; i++) {
// 加入新字符
windowCount[s.charAt(i) - 'a']++;
// 移除旧字符
windowCount[s.charAt(i - pLen) - 'a']--;
// 检查当前窗口是否匹配
if (Arrays.equals(pCount, windowCount)) {
result.add(i - pLen + 1);
}
}
return result;
}
}
⚡ 优化版：使用“匹配计数器”避免全数组比较
可以进一步优化，不每次都调用 Arrays.equals（虽然 26 是常数，但可更优雅）：
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
int sLen = s.length(), pLen = p.length();
if (sLen < pLen) return result;
int[] count = new int[26];
for (char c : p.toCharArray()) count[c - 'a']++;
int left = 0, match = 0;
for (int right = 0; right < sLen; right++) {
char cR = s.charAt(right);
if (--count[cR - 'a'] >= 0) match++; // 该字符是 p 中需要的
if (right >= pLen) {
char cL = s.charAt(left++);
if (++count[cL - 'a'] > 0) match--; // 移除后，若变正，说明少了一个有效字符
}
if (match == pLen) {
result.add(left);
}
}
return result;
}
这种写法更紧凑，但理解稍难。推荐掌握第一种清晰版本。
⏱️ 复杂度分析
- 时间复杂度：O(n)，其中 n =
s.length()（每个字符访问常数次） - 空间复杂度：O(1)（两个长度为 26 的数组，视为常数空间）
✅ 总结
- 核心思想：异位词 ⇨ 字符频次相同
- 技巧：固定长度滑动窗口 + 频次数组
- 变种题：LeetCode 567（判断是否存在异位词子串）