本题采用基于单频次数组维护的滑动窗口算法解决“找到字符串中所有字母异位词”问题。其核心本质是通过将目标字符串的字符频次初始化为正计数并在窗口扩张时进行扣减利用出现负计数作为非合法状态信号来驱动左指针收缩。该解法消除了每轮迭代中对两个频次数组进行线性比对的开销最终走向是通过单次线性扫描精确锁定所有满足长度和频次双重约束的子串起始索引。一、 问题本质与数据模型字母异位词的物理特性是字符种类相同、各个字符出现的频次完全相同、字符串长度相等。在长字符串 s 中寻找目标字符串 p 的字母异位词可以转化为在 s 上维护一个大小动态趋向于 p.length() 的滑动窗口 [left, right]。为了实现高效率的匹配判定算法构建了一个大小为 26 的整型数组 cnt对应 26 个小写英文字母。该数组既是目标字符的“账本”又是窗口状态的“计数器”初始化阶段遍历字符串 p统计其中每个字符出现的次数并在 cnt 对应位置进行加和。此时cnt 中大于 0 的值代表窗口需要覆盖的字符缺口。滑动阶段右指针 right 引入字符时对 cnt 执行扣减消费缺口。左指针 left 移出字符时对 cnt 执行加回释放资源。二、 算法演进对比在解决此类子串多点匹配问题时单数组滑动窗口法在时空复杂度上均达到了理论极限解法名称时间复杂度空间复杂度核心原理物理瓶颈暴力枚举法O(n * m)O(m)枚举所有长度为 m 的子串对其进行排序或频次统计比对存在大量重复的区间扫描时间效率低下双数组滑动窗口O(n * 26) O(n)O(26) O(1)维护窗口频次数组与目标频次数组每轮循环线性比对两个数组是否完全一致每次右移都需要执行最多 26 次的比对操作单数组滑动窗口当前解法O(n)O(26) O(1)利用单个数组的负数值作为冲突信号通过长度匹配隐式确立完全一致性无消除数组比对开销每个字符最多被访问两次(其中 n 为字符串 s 的长度m 为字符串 p 的长度)三、 滑动窗口核心逻辑拆解当前解法的妙处在于它不需要在每一步都去对比 26 个字母的频次是否完全相等而是通过“控制负数”和“匹配长度”来隐式推导合法性。1. 冲突触发与消除机制每当右指针右移并移入一个字符c时直接执行cnt[c]--。如果字符c原本不在字符串 p 中或者它在当前窗口内的数量已经超过了 p 中的核定数量那么执行扣减后cnt[c]必然会变为负数即cnt[c] 0。一旦出现cnt[c] 0说明当前窗口处于非法状态。此时立即触发while循环左指针开始向右收缩沿途将移出的字符在cnt中执行加回cnt[s.charAt(left)]直到把多余的c移出窗口使cnt[c]重新恢复到 0循环才会停止。2. 合法异位词的判定当程序流通过了while循环意味着当前cnt数组中没有任何一个位置的值是负数。此时如果窗口的实际物理长度right - left 1恰好等于字符串 p 的长度p.length()由于总字符数相等且没有任何字符超标无负数在数学上可以绝对推导出当前窗口内的字符频次与 p 完全一致。因此left索引即为一个合法的字母异位词起点。四、 算法执行状态机步进示例以输入数据s abab,p ab为例初始cnt[a]1,cnt[b]1其状态机的演进过程如下表所示步骤指针状态移入字符cnt 数组关键状态while 收缩逻辑窗口物理长度判定结果集 ans初始化left0-cnt[a]1, cnt[b]1窗口未启动-[]第 1 步left0, right0acnt[a]0cnt[a]不小于0跳过0-01 1 ! 2[]第 2 步left0, right1bcnt[b]0cnt[b]不小于0跳过1-01 2 2 (合法)[0]第 3 步left0, right2acnt[a]-1触发收缩移出s0, cnt[a]0, left1退出循环2-11 2 2 (合法)[0,1]第 4 步left1, right3bcnt[b]-1触发收缩移出s1, cnt[b]0, left2退出循环3-21 2 2 (合法)[0, 1,2]五、 Java 源码实现含标准注释class Solution { public ListInteger findAnagrams(String s, String p) { // 用于存储所有合法字母异位词的起始索引 ListInteger ans new ArrayList(); // 边界情况处理若 s 的长度小于 p则无法在 s 中找到 p 的异位词 if (s.length() p.length()) { return ans; } // 频次统计数组由于题目明确限制仅包含小写字母使用 26 位大小的空间即可 int[] cnt new int[26]; for (char c : p.toCharArray()) { cnt[c - a]; } int left 0; // 右指针作为主循环变量负责无条件向右扩展窗口 for (int right 0; right s.length(); right) { int c s.charAt(right) - a; // 进入窗口的字符其可消费额度自减 cnt[c]--; // 如果当前字符对应的计数小于 0说明当前窗口引入了无效字符或者该字符数量溢出 while (cnt[c] 0) { // 左指针向右收缩沿途释放字符额度 cnt[s.charAt(left) - a]; left; } // 经过上述 while 循环后窗口内部状态必然恢复合法即没有字符超标 // 此时若窗口长度等于 p 的长度说明找到了一个完整的异位词 if (right - left 1 p.length()) { ans.add(left); } } return ans; } }六、 复杂度分析1. 时间复杂度O(n)执行轨迹虽然结构上存在嵌套循环但右指针right随着for循环从0递增到s.length() - 1一共移动了 n 次。左指针left只在while内部进行递增操作在整个算法生命周期中left最多也只能移动 n 次。结论字符串s中的每个字符在滑动过程中最多被右指针移入窗口一次被左指针移出窗口一次。整体的基本操作执行次数与 n 呈标准的线性正比关系其中 n 为字符串s的长度。2. 空间复杂度O(1)分配机制算法内部独立申请的辅助存储空间为一个固定容量的整型数组cnt[26]以及常数个基础类型的控制变量left,right,c。结论所占用的常数阶存储空间是由小写英文字母的字符集大小固定值 26决定的完全独立于输入字符串s和p的规模因此空间复杂度为稳定的 O(1)。