网硕互联帮助中心👋 欢迎阅读
一.题目
438. 找到字符串中所有字母异位词 – 力扣（LeetCode）
🎯 欢迎来到「找到字符串中所有字母异位词」题解之旅！ 本文将带你从"在长串中滑动窗口寻找异位词"这一直观场景出发，深入理解滑动窗口 + 计数数组的巧妙运用，并掌握如何用有效计数 count 判断命中来定位全部异位词起点。
在开始之前，建议你先：
-
了解题目背景：这是 LeetCode 438 题，给定字符串 s 和 p，找出 s 中所有 p 的字母异位词子串起始下标。本质上，异位词即各字母出现次数相同，问题转化为定长窗口内的计数比对。
-
明确学习目标：掌握滑动窗口 + 双计数数组技术，理解有效计数 count 的维护原理，并熟练处理窗口超长时的出窗口逻辑。
-
准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如 s = "cbaebabacd", p = "abc" 输出 [0, 6]）。
本文将从问题转化、进窗口、出窗口、更新结果到代码实现，层层递进。即使你对滑动窗口还不熟悉，我们也会从"让窗口与 p 等长，边走边核对字母账本"这一直觉出发，让你轻松抓住核心思想——窗口定长滑动，计数对齐即命中。现在，让我们一起滑动窗口，找出所有字母异位词的起点吧！ 📍🔍
二.做题思路
一、问题分析（前置分析）
- 题目要求：在 s 中找出所有与 p 互为字母异位词的连续子串，返回其起始下标。
- 关键约束：子串长度必须等于 p 的长度（定长窗口）；仅含小写字母（可用 26 长度计数数组）；异位词只看字符频次相等，与顺序无关。
- 核心思路：维护长度恒为 n1 的滑动窗口，用有效计数 count 把 O(26) 的频次比对压缩为 O(1) 的整数判断。
二、算法策略（滑动窗口 + 计数数组）
核心步骤：
示例执行过程（s = "cbaebabacd"，p = "abc"，n1 = 3）：
| 预处理 | hash1[a]=1, b=1, c=1 | 统计 p 的频次 | 计数表就绪 |
| right=0 | hash2[c]=1, count=1 | 进 'c'，配额内 | 未命中 |
| right=1 | hash2[b]=1, count=2 | 进 'b'，配额内 | 未命中 |
| right=2 | hash2[a]=1, count=3 | 进 'a'，配额内，窗口=3 | 命中，记录 left=0 |
| right=3 | count: 3→2, left=1 | 进 'e' 不计；出 'c' 减 count | 未命中 |
| … | … | … | … |
| right=8 | count: 2→3, left=6 | 进 'c' 计 1；出 'a' 不减 | 命中，记录 left=6 |
| right=9 | count: 3→2, left=7 | 进 'd' 不计；出 'b' 减 count | 未命中 |
最终返回 [0, 6]，与题目示例一致。
三、正确性说明（简单版本）
- 窗口长度恒为 n1：每次右指针前进后，只要长度超过 n1 就立刻收缩左端，保证被判断的窗口始终与 p 等长，不漏检也不重检。
- count 语义可靠：count 表示窗口中"有效字符"总数——即每个字符在不超过 p 需求配额内的累计数量。只有当 count == n1 时，窗口内频次才恰好全部等于 p 的需求，此时窗口必然是异位词；反之亦然，不会错解。
- 每个起点都被覆盖：left 从 0 一路右移到 n2 – n1，所有可能的定长子串恰好被窗口完整覆盖一次，不会漏解。
- 出窗口判定安全：先依据移除前的频次判断是否 count–，再真正减频次，顺序保证 count 始终准确。
四、实现细节（边界防护）
- 初始化：hash1[26] = {0}、hash2[26] = {0}、left = 0、right = 0、count = 0、n1 = p.size()、n2 = s.size()。
- 边界防护：若 n1 > n2，s 中不可能存在长度 n1 的异位词子串，直接返回空；right 遍历到 n2 即停；字符统一用 ch – 'a' 映射到 0~25。
- 复杂度：时间 O(n2)（每个字符进、出窗口各一次，count 判断 O(1)），空间 O(1)（两个固定长度 26 的数组）。
- 关键判断：if (hash2[in] <= hash1[in]) count++（进窗口配额判断）、if (right – left + 1 > n1)（窗口收缩判断）、if (count == n1)（命中判断）。
五、返回值（目标映射）
- 返回 v：所有满足条件的子串起始下标。由于 left 从左向右移动，结果自然升序排列，正好对应题目要求的"返回所有起始索引"。
三.代码
class Solution
{
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> v; // 结果数组：记录所有异位词子串的起始下标
int n1 = p.size(); // p 的长度，即窗口的固定长度
int n2 = s.size();
// 边界防护：s 比 p 短，不可能存在异位词子串，直接返回空
if (n1 > n2)
{
return v;
}
int hash1[26] = { 0 }; // p 的频次表：记录 p 中每个字母的出现次数
// 1. 预处理：统计 p 中各字符频次
for (auto ch : p)
{
hash1[ch – 'a']++; // 'a' 的 ASCII 码是 97，统一映射到 0~25
}
int hash2[26] = { 0 }; // 窗口频次表：记录当前窗口内各字符出现次数
// 2. 滑动窗口：进窗口 -> 判断/出窗口 -> 更新结果
for (int left = 0, right = 0, count = 0; right < n2; right++)
{
// ———- 进窗口 ———-
int in = s[right] – 'a'; // 进入窗口的字符
hash2[in]++; // 窗口频次 +1
if (hash2[in] <= hash1[in])
{
count++; // 该字符仍在 p 的“配额”内，有效计数 +1
}
// ———- 判断 / 出窗口 ———-
if (right – left + 1 > n1) // 窗口长度超出 p 的长度，必须收缩
{
int out = s[left] – 'a'; // 即将离开窗口的字符
if (hash2[out] <= hash1[out])
{
count–; // 移除前该字符曾计入配额，有效计数 -1
}
hash2[out]–; // 窗口频次 -1
left++; // 左指针右移，窗口恢复为 n1 长度
}
// ———- 更新结果 ———-
if (count == n1) // 有效计数等于 p 长度，说明频次完全匹配
{
v.push_back(left); // 记录当前窗口起点
}
}
return v; // 3. 返回所有异位词起始下标
}
};
四、易错点分析
难点1：进窗口时"先加频次，再判断配额"的顺序
hash2[in]++;
if (hash2[in] <= hash1[in])
{
count++;
}
count 统计的是窗口中未超出 p 配额的字符个数。进窗口时判断依据必须是加入后的最新频次，所以必须先 hash2[in]++ 再比较；若顺序颠倒，就会用旧频次误判，导致 count 偏小、漏解。
难点2：出窗口时 count– 的判断基于"移除前"的频次
int out = s[left] – 'a';
if (hash2[out] <= hash1[out])
{
count–;
}
hash2[out]–;
这里判断的是"该字符被移除前是否处于配额内"。如果先 hash2[out]– 再判断，频次已减少，结果可能失真（例如原频次恰好超配额 1，先减后判变成"在配额内"，导致 count 漏减）。判断与修改的先后顺序是本题最容易写错的地方。
难点3：count 不是"窗口字符总数"，而是"有效字符总数"
if (count == n1)
{
v.push_back(left);
}
窗口里可能混入 p 中没有的字符（如 'e'、'd'），它们不计入 count；同一字符超出配额的重复出现也不计入。只有 count == n1 时，窗口内频次才与 p 完全一致。把 count 误当成窗口长度是常见的理解误区。
难点4：窗口收缩条件 > 与 >= 的一字之差
if (right – left + 1 > n1)
{
…
left++;
}
窗口长度必须恰好等于 n1：短了会漏检，长了会重复。用 > 保证每轮至多收缩一次，窗口稳定在 n1；若误写成 >=，窗口会被压到 n1-1，导致永远无法命中，返回空数组。
五、流程图
🎯 闭幕
🎉 恭喜你完成了「找到字符串中所有字母异位词」问题的学习！
为了巩固知识并进一步拓展，建议你：
🚀 动手实践 在 LeetCode 上提交代码，尝试不同的测试用例。
💡 深入思考
-
本题使用 固定长度的滑动窗口（窗口大小固定为 p.length()），并通过 数组哈希表 统计窗口内字符频次与 p 的频次进行比较。请问 为什么窗口长度固定为 p 的长度？如果窗口长度不固定，还能用这种方式吗？
-
代码中通过 count 变量记录 有效字符数（即窗口内频次不超过 p 对应频次的字符个数），从而避免每次完整比较两个哈希表。为什么 count == n1 就能说明窗口是异位词？ 这背后的等价条件是什么？
-
当窗口长度超过 n1 时，代码先判断 hash2[out] <= hash1[out] 再 count–，然后再 hash2[out]–。为什么先判断再减，而不是先减再判断？ 顺序颠倒会有什么问题？
-
本题字符集限定为 小写英文字母，所以用 int hash[26] 足够。如果字符串包含 Unicode 字符（如中文），应如何改造代码？
-
滑动窗口的 “进窗口 → 判断/出窗口 → 更新结果” 三段式结构是本题模板的典型写法。如果将出窗口放在 更新结果之后（即先判断再收缩），会有什么影响？
📚 延伸挑战
-
如果题目要求返回 所有异位词子串本身（而不是起始下标），你的代码应做哪些调整？
-
如果 p 中可能包含 重复字符（例如 p = "aa"），当前的 count 计数逻辑是否仍然正确？请结合示例 s = "baa" 验证。
如果你觉得本文对你有所帮助，欢迎：
👍 点赞 / 收藏 👤 关注作者，获取更多题解 💬 留言交流你的疑问或优化思路
📌 深入思考答案
-
窗口长度固定为 n1，因为异位词要求 长度相同且字符频次相同，长度不同则不可能匹配，因此固定窗口长度是自然的约束。
-
count == n1 等价于完全匹配，因为 count 记录的是窗口内所有字符的频次都不超过 p 中对应字符频次的数量，且窗口长度等于 n1，这意味着窗口内每个字符的频次恰好等于 p 中对应字符的频次，即完全匹配。
-
必须先判断再减，因为判断的是 移除前 该字符是否在 p 的配额内，若先减再判断，hash2[out] 已变化，判断结果会错误，导致 count 计数不准。
-
若字符集为 Unicode，改用 unordered_map<char, int> 替代固定数组，动态统计频次，适应任意字符。
-
若先更新结果再收缩，会导致窗口长度大于 n1 时仍可能被判断为有效，破坏固定窗口的语义，必须先在更新结果前确保窗口长度合法。
🔍 延伸挑战答案
-
挑战1：只需在 v.push_back(left) 的同时，用 s.substr(left, n1) 取出子串并存入结果数组即可。
-
挑战2：count 逻辑仍然正确。以 s="baa", p="aa" 为例：初始窗口 "ba"，count 中 b 频次 1 > hash1['b']=0，不计入；a 频次 1 ≤ hash1['a']=2，计入，count=1，不满足 count==2。右移后窗口 "aa"，两个 a 均计入，count=2，匹配，逻辑无误。
祝你在 算法之路 上越走越稳，早日攻克每一道难题！下次见 🚀✨
评论前必须登录！
注册