欢迎阅读一.题目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) 的整数判断。二、算法策略滑动窗口 计数数组核心步骤统计p中各字符频次到hash1[26]。初始化窗口left 0、right 0、count 0hash2[26]记录窗口内频次。进窗口right指向的字符加入hash2若加入后hash2[ch] hash1[ch]说明该字符仍在配额内count。出窗口当窗口长度right - left 1 n1时移除left指向的字符若移除前hash2[ch] hash1[ch]说明它曾计入配额count--再hash2[ch]--、left。更新结果若count n1说明窗口内频次与p完全一致记录left。示例执行过程s cbaebabacdp abcn1 3步骤变量变化操作结果预处理hash1[a]1, b1, c1统计 p 的频次计数表就绪right0hash2[c]1, count1进 c配额内未命中right1hash2[b]1, count2进 b配额内未命中right2hash2[a]1, count3进 a配额内窗口3命中记录 left0right3count: 3→2, left1进 e 不计出 c 减 count未命中…………right8count: 2→3, left6进 c 计 1出 a 不减命中记录 left6right9count: 3→2, left7进 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 n2s 中不可能存在长度 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: vectorint findAnagrams(string s, string p) { vectorint 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 漏减。判断与修改的先后顺序是本题最容易写错的地方。难点3count 不是窗口字符总数而是有效字符总数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_mapchar, int替代固定数组动态统计频次适应任意字符。若先更新结果再收缩会导致窗口长度大于n1时仍可能被判断为有效破坏固定窗口的语义必须先在更新结果前确保窗口长度合法。延伸挑战答案挑战1只需在v.push_back(left)的同时用s.substr(left, n1)取出子串并存入结果数组即可。挑战2count逻辑仍然正确。以sbaa, paa为例初始窗口bacount中b频次 1 hash1[b]0不计入a频次 1 ≤hash1[a]2计入count1不满足count2。右移后窗口aa两个a均计入count2匹配逻辑无误。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨ 欢迎阅读一.题目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) 的整数判断。二、算法策略滑动窗口 计数数组核心步骤统计p中各字符频次到hash1[26]。初始化窗口left 0、right 0、count 0hash2[26]记录窗口内频次。进窗口right指向的字符加入hash2若加入后hash2[ch] hash1[ch]说明该字符仍在配额内count。出窗口当窗口长度right - left 1 n1时移除left指向的字符若移除前hash2[ch] hash1[ch]说明它曾计入配额count--再hash2[ch]--、left。更新结果若count n1说明窗口内频次与p完全一致记录left。示例执行过程s cbaebabacdp abcn1 3步骤变量变化操作结果预处理hash1[a]1, b1, c1统计 p 的频次计数表就绪right0hash2[c]1, count1进 c配额内未命中right1hash2[b]1, count2进 b配额内未命中right2hash2[a]1, count3进 a配额内窗口3命中记录 left0right3count: 3→2, left1进 e 不计出 c 减 count未命中…………right8count: 2→3, left6进 c 计 1出 a 不减命中记录 left6right9count: 3→2, left7进 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 n2s 中不可能存在长度 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: vectorint findAnagrams(string s, string p) { vectorint 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 漏减。判断与修改的先后顺序是本题最容易写错的地方。难点3count 不是窗口字符总数而是有效字符总数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_mapchar, int替代固定数组动态统计频次适应任意字符。若先更新结果再收缩会导致窗口长度大于n1时仍可能被判断为有效破坏固定窗口的语义必须先在更新结果前确保窗口长度合法。延伸挑战答案挑战1只需在v.push_back(left)的同时用s.substr(left, n1)取出子串并存入结果数组即可。挑战2count逻辑仍然正确。以sbaa, paa为例初始窗口bacount中b频次 1 hash1[b]0不计入a频次 1 ≤hash1[a]2计入count1不满足count2。右移后窗口aa两个a均计入count2匹配逻辑无误。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨ 
