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

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

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

整体思路

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

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

1. 初始化“需求”计数器：

   • 算法使用一个大小为 26 的整型数组 cnt。这个数组的含义非常关键：它首先被初始化为模式串 p 的字符频率，代表着我们“需要”的字符及其数量。
   • 例如，如果 p = "aab"，则 cnt['a'-'a'] 为 2，cnt['b'-'a'] 为 1。

2. 滑动窗口的扩张与收缩：

   • 算法使用 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] 不再为负。

3. 判定与记录结果：

   • 在每一次 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 是滑动窗口的右边界，它将遍历整个主串 s
        for (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)

1. 模式串频率统计：for (char ch : p.toCharArray()) 循环遍历模式串 p 一次，时间复杂度为 O(M)，其中 M 是 p 的长度。
2. 滑动窗口遍历：
   • 外层的 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)

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

综合分析：
算法所需的额外辅助空间主要由 cnt 数组决定。由于其大小是固定的，空间复杂度为 O(k)，其中 k=26。因为 k 是一个常数，所以通常也称其空间复杂度为 O(1)。