找到字符串中所有字母异位词
给定两个字符串 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 * 10^4 s 和 p 仅包含小写字母
第一次解答：滑动窗口 + 排序对比
解题思路
核心方法：滑动窗口 + 排序对比。通过固定长度的滑动窗口遍历 s 的所有子串，将子串和 p 分别排序后对比是否相等，以此判断是否为异位词，逻辑直观但时间效率极低。
具体步骤：
- 初始化结果列表
result，用于存储符合条件的子串起始索引。 - 定义滑动窗口的左右边界：
left初始为 0，right初始为 p 的长度（窗口长度固定为 p 的长度，因为异位词长度必与 p 相同）。 - 预处理 p 字符串：将 p 转为字符数组并排序（
Arrays.sort(pArray)），得到 p 的'标准有序形式'（异位词排序后结果相同）。 - 滑动窗口遍历 s 字符串（终止条件：
right <= s.length()）： a. 截取当前窗口内的子串s1 = s.substring(left, right)； b. 将 s1 转为字符数组并排序（Arrays.sort(s1Array)）； c. 对比排序后的 s1 数组和 p 数组是否相等：若相等，说明当前子串是 p 的异位词，将left加入结果列表； d. 窗口右移：left++、right++，继续检查下一个窗口。 - 遍历完成后，返回结果列表
result。
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
int left = 0;
int right = p.length();
char[] pArray = p.toCharArray();
Arrays.sort(pArray);
while (right <= s.length()) {
String s1 = s.substring(left, right);
char[] s1Array = s1.toCharArray();
Arrays.sort(s1Array);
if (Arrays.equals(pArray, s1Array)) {
result.add(left);
}
left++;
right++;
}
return result;
}
失败/性能劣势原因分析
该解法耗时极长且仅击败极少数用户，核心问题是时间复杂度过高，无法适配题目数据规模：
- 时间复杂度为 O(n×m×logm)（n 为 s 的长度，m 为 p 的长度）：
- 滑动窗口遍历 s 需执行 n - m + 1 次（约 O(n)）；
- 每次遍历需对窗口子串（长度 m）和 p（长度 m）分别排序，排序的时间复杂度为 O(m×logm)；
- 总计算量约为 O(n×m×logm)，对于极端情况，计算量会远超时间阈值，导致耗时极长。
- 冗余操作：每次窗口滑动都要重新截取子串、转数组、排序，存在大量重复计算（如相邻窗口仅首尾字符不同，却要对整个子串重新排序）。
- 内存表现差：频繁的字符串截取、数组转换操作会产生大量临时对象，导致内存消耗偏高。
第二次解答：滑动窗口 + 字符计数对比
解题思路
核心方法：滑动窗口 + 字符计数对比。利用'异位词的字符出现次数完全相同'的特性，通过数组统计字符频次，替代排序对比，将时间复杂度优化至 O(n)，大幅提升性能。
具体步骤：
- 核心原理铺垫：异位词的本质是'每个字符的出现次数完全一致'，因此无需排序，只需统计 26 个小写字母的出现次数，对比频次数组即可判断是否为异位词。
- 初始化两个长度为 26 的数组（对应 26 个小写字母）：
pCount：统计 p 中每个字符的出现次数；sCount：统计 s 中当前滑动窗口内每个字符的出现次数。
- 预处理 p 的字符频次：遍历 p 的每个字符，通过
p.charAt(i)-'a'将字符映射为 0-25 的数组索引，对应位置计数加 1（如字符'a'对应索引 0，'b'对应索引 1）。 - 滑动窗口统计 s 的字符频次：遍历 s 的每个字符（索引 i）：
a. 将当前字符的频次计入
sCount（sCount[s.charAt(i)-'a']++）； b. 若i >= p.length()（窗口长度超过 p 的长度），需移除窗口左侧的字符频次：sCount[s.charAt(i-p.length())-'a']--（保证sCount仅统计当前窗口内的字符）； c. 对比pCount和sCount是否相等：若相等，说明当前窗口内的子串是 p 的异位词，计算子串起始索引（i - p.length() + 1）并加入结果列表。 - 遍历完成后，返回结果列表
result。
核心优化逻辑说明
- 时间复杂度优化：
- 预处理 p 的频次：O(m)（m 为 p 的长度）；
- 遍历 s 统计频次：O(n)（n 为 s 的长度），每个字符仅执行'计数 +1/计数 -1'的 O(1) 操作；
- 对比频次数组：
Arrays.equals对比 26 个元素，属于 O(1) 操作； - 总时间复杂度为 O(n + m)，接近 O(n)，相比第一次解答的 O(n×m×logm)，性能提升数个量级。
- 空间优化：仅使用两个长度为 26 的固定数组（总占用 52 个 int 空间），无频繁的字符串/数组临时对象创建。
- 滑动窗口的高效性：窗口移动时仅更新首尾字符的频次，无需重新处理整个窗口，消除了第一次解答的重复排序开销。
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
int[] pCount = new int[26];
int[] sCount = new int[26];
// 因为 ASCII 码差值计算，小写字母 'a' 到 'z' 在 ASCII 表中是连续编码的
// 'a' -> ASCII 值 97，'b' -> 98，...，'z' -> 122
// 字符 - 'a' 的结果：'a' - 'a' = 0，'b' - 'a' = 1，...，'z' - 'a' = 25
// 这样就将 26 个字母映射到 0~25 的整数，完美对应数组索引。
for (int i = 0; i < p.length(); i++) {
pCount[p.charAt(i) - 'a']++;
}
for (int i = 0; i < s.length(); i++) {
sCount[s.charAt(i) - 'a']++;
if (i >= p.length()) {
// 移出第一个字符的数量
sCount[s.charAt(i - p.length()) - 'a']--;
}
// 判断是否相等
if (Arrays.equals(pCount, sCount)) {
result.add(i - p.length() + 1);
}
}
return result;
}
总结
- 第一次解答的'排序对比'思路逻辑直观，但排序带来的 O(m×logm) 开销导致时间复杂度极高，仅适用于极小数据量，无法满足题目要求；
- 第二次解答的'字符计数'思路是本题的最优解：利用异位词的字符频次特性，用固定长度的数组替代排序，将时间复杂度优化至 O(n)，是'空间换时间'的经典应用；
- 本题的核心优化方向是：放弃'排序后对比'的直观思路，转而利用'字符频次相等'的本质特征，通过高效的计数操作替代高开销的排序操作。
