当前位置：首页 > news >正文

【LeetCode 热题 100】438. 找到字符串中所有字母异位词——（解法三）不定长滑动窗口+数组

news 2025/6/29 11:16:38

Problem: 438. 找到字符串中所有字母异位词
题目：给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

【LeetCode 热题 100】438. 找到字符串中所有字母异位词——（解法一）定长滑动窗口+哈希表
【LeetCode 热题 100】438. 找到字符串中所有字母异位词——（解法二）定长滑动窗口+数组

整体思路

这段代码同样用于在字符串 s 中查找所有模式串 p 的异位词。它采用了一种更为巧妙和高效的 可变大小滑动窗口 算法。与前两个版本（一个用 HashMap，一个用固定大小窗口的数组）相比，此版本的核心思想是维护一个“合法”的窗口，该窗口内的字符都是 p 所需要的。

算法的整体思路可以分解为以下步骤：

初始化“需求”计数器：
- 算法使用一个大小为 26 的整型数组 cnt。这个数组的含义非常关键：它首先被初始化为模式串 p 的字符频率，代表着我们“需要”的字符及其数量。
- 例如，如果 p = "aab"，则 cnt['a'-'a'] 为 2，cnt['b'-'a'] 为 1。
滑动窗口的扩张与收缩：
- 算法使用 left 和 right 两个指针来定义滑动窗口 [left, right]。right 指针持续向右移动，以扩大窗口。
- 扩张与“消耗”：当 right 指针扫过 s 中的一个字符 c 时，会执行 cnt[c]--。这可以理解为“消耗”掉了一个所需的字符 c。
  - 如果消耗后 cnt[c] 仍 >= 0，说明这个字符是 p 所需要的，且目前窗口内该字符的数量尚未超出 p 的需求。
  - 如果消耗后 cnt[c] < 0，这说明窗口内已经包含了多余的字符 c（即超出了 p 的需求量）。
- 收缩以维持“合法性”：
  - 一旦 cnt[c] 变为负数，就触发 while 循环。这个循环的目的是收缩窗口的左边界 left，直到窗口再次变得“合法”。
  - 收缩时，将 left 指针指向的字符“归还”给计数器（cnt[s.charAt(left) - 'a']++），然后将 left 右移。
  - 这个过程会一直持续，直到我们刚刚加入的那个多余字符 c 的计数 cnt[c] 不再为负。
判定与记录结果：
- 在每一次 right 指针移动后（并可能伴随着 left 的移动），算法会检查当前窗口 [left, right] 的大小。
- 如果窗口大小 right - left + 1 正好等于模式串 p 的长度 m，这意味着：
  1. 窗口内没有多余的字符（因为 while 循环保证了所有 cnt 值都 >= 0）。
  2. 窗口的总字符数正好是 m。
- 这两个条件同时满足的唯一情况就是：窗口内的字符频率与 p 完全匹配。因此，这是一个异位词，将其起始索引 left 加入结果列表。

这种方法的精髓在于，它不强制窗口大小始终为 m，而是灵活地收缩窗口以排出“无效”字符，一旦窗口在“有效”状态下长度恰好为 m，就找到了一个解。

完整代码

import java.util.ArrayList;
import java.util.List;class Solution {/*** 在字符串 s 中查找 p 的所有异位词的起始索引。* 此版本使用可变大小的滑动窗口和单个计数数组，非常高效。* @param s 主字符串 (假定只包含小写字母)* @param p 模式字符串 (假定只包含小写字母)* @return 一个包含所有匹配起始索引的列表*/public List<Integer> findAnagrams(String s, String p) {// ans 用于存储结果，即所有异位词的起始索引List<Integer> ans = new ArrayList<>();int n = s.length();int m = p.length();// 如果主串比模式串还短，直接返回空列表if (n < m) {return ans;}// cnt 数组作为字符频率计数器。// 初始时，它存储了模式串 p 中需要的各个字符的数量。int[] cnt = new int[26];for (char ch : p.toCharArray()) {cnt[ch - 'a']++;}// left 是滑动窗口的左边界int left = 0;// right 是滑动窗口的右边界，它将遍历整个主串 sfor (int right = 0; right < n; right++) {// 获取右边界字符并将其映射到索引int c = s.charAt(right) - 'a';// 将该字符的所需数量减 1，表示窗口“消耗”了该字符。cnt[c]--;// 关键逻辑：处理窗口内字符冗余的情况。// 如果 cnt[c] < 0，说明窗口内字符 c 的数量已经超出了 p 的需求。// 此时需要从左侧收缩窗口，直到 cnt[c] 恢复到 0。while (cnt[c] < 0) {// "归还" 左边界字符：将其在 cnt 数组中的计数加 1。cnt[s.charAt(left) - 'a']++;// 移动左边界，缩小窗口。left++;}// 检查窗口大小是否等于模式串的长度。// 因为 while 循环保证了窗口内没有多余字符（所有 cnt[i] >= 0），// 如果此时窗口大小恰好为 m，那么它必然是一个异位词。if (right - left + 1 == m) {ans.add(left);}}// 返回最终的结果列表return ans;}
}

时空复杂度

时间复杂度：O(N + M)

模式串频率统计：for (char ch : p.toCharArray()) 循环遍历模式串 p 一次，时间复杂度为 O(M)，其中 M 是 p 的长度。
滑动窗口遍历：
- 外层的 for 循环由 right 指针驱动，从 0 到 n-1，所以 right 指针总共移动了 N 次。
- 内层的 while 循环由 left 指针驱动。虽然它在 for 循环内部，但 left 指针也只是一直向右移动，永不后退。
- 在整个算法的生命周期中，left 指针最多从 0 移动到 n。
- 每个字符 s.charAt(i) 最多被 right 指针访问一次，也最多被 left 指针访问一次。因此，两个指针的总移动次数是线性的，约为 2N。
- 所有数组操作 cnt[...]-- 和 cnt[...]++ 都是 O(1) 的。

综合分析：
总的时间复杂度是预处理 p 的时间加上两个指针遍历 s 的时间，即 O(M) + O(N) = O(N + M)。这是一个非常高效的线性时间复杂度。

空间复杂度：O(k) 或 O(1)

主要存储开销：算法只使用了一个额外的整型数组 cnt。
- 该数组的大小是 26，这是一个固定的常数，代表了字符集的大小（k=26）。它不随输入 s 或 p 的长度而改变。
结果列表：ans 列表用于存储输出，其空间不计入算法的辅助空间复杂度。
其他变量：n, m, left, right, c 等都占用常数空间 O(1)。