14.LeetCode 438 题解：滑动窗口+哈希表找所有字母异位词
目录
一、题目解析
二、讲解算法原理
1. 如何快速判断两个字符串是否是“异位词”？
2. 解决问题：滑动窗口 + 哈希表
三、解决问题（滑动窗口 + 哈希表流程）
四、优化：更新结果的判断条件
五、完整代码（Java）
一、题目解析
题目：438. 找到字符串中所有字母异位词
链接：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）
题目描述：给定两个字符串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]
二、讲解算法原理
1. 如何快速判断两个字符串是否是“异位词”？
利用哈希表。例如：
字符串
s1 = "aabca"：统计每个字符出现次数 →a→3, b→1, c→1（记为hash1）。字符串
s2 = "abaca"：统计每个字符出现次数 →a→3, b→1, c→1（记为hash2）。若
hash1和hash2完全相同，则两字符串是异位词。
2. 解决问题：滑动窗口 + 哈希表
核心思路：用滑动窗口维护s中与p长度相同的子串，用哈希表统计窗口内字符与p的字符频次，判断是否匹配。
三、解决问题（滑动窗口 + 哈希表流程）
初始化窗口：
left = 0,right = 0。进窗口：将
s[right]加入窗口，更新窗口字符的哈希表（hash2）。判断窗口长度：若
right - left + 1 > p.length()，则需要出窗口（移除s[left]），更新hash2。更新结果：检查
hash2与p的哈希表（hash1）是否匹配，若匹配则记录起始索引left。
四、优化：更新结果的判断条件
利用变量count统计窗口中“有效字符”的个数（即窗口内字符频次 ≤p中对应字符频次的字符数量）。
进窗口：进入字符后，若
hash2[in] ≤ hash1[in]，则count++（说明该字符是“有效”的）。出窗口：离开字符前，若
hash2[out] ≤ hash1[out]，则count--（说明该字符离开后，“有效”字符减少）。更新结果：当
count == p.length()时，说明窗口内所有字符都“有效”，即找到异位词，记录left。
五、完整代码（Java）
class Solution { public List<Integer> findAnagrams(String ss, String pp) { List<Integer> ret = new ArrayList<Integer>(); char[] s = ss.toCharArray(); char[] p = pp.toCharArray(); int[] hash1 = new int[26]; // 统计字符串 p 中每一个字符出现的个数 for (char ch : p) hash1[ch - 'a']++; int[] hash2 = new int[26]; // 统计窗口中每一个字符出现的个数 int m = p.length; for (int left = 0, right = 0, count = 0; right < s.length; right++) { char in = s[right]; if (++hash2[in - 'a'] <= hash1[in - 'a']) count++; // 进窗口 + 维护 count if (right - left + 1 > m) // 判断窗口长度是否超过 p 的长度 { char out = s[left++]; if (hash2[out - 'a']-- <= hash1[out - 'a']) count--; // 出窗口 + 维护 count } // 更新结果：当 count == m 时，说明窗口内是异位词 if (count == m) ret.add(left); } return ret; } }