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

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

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

整体思路

这段代码同样旨在解决 “在一个字符串 s 中找出所有模式串 p 的异位词” 的问题。与上一个使用 HashMap 的版本相比，此版本采用了 固定大小的数组 作为频率计数的工具，这是一种针对特定字符集（此处为小写英文字母）的常见优化。

算法的核心思路依然是 滑动窗口，但具体实现细节有所不同：

1. 数据结构选择与预处理：

   • 该实现选择了两个大小为 26 的整型数组 cntP 和 cntS 来分别存储模式串 p 和当前滑动窗口的字符频率。
   • 前提与优势：这个选择基于一个重要假设——输入字符串 s 和 p 只包含小写英文字母。利用 char - 'a' 的技巧，可以将每个字符映射到数组的 0-25 索引上，这比 HashMap 更快且内存占用更低。
   • 首先，代码遍历模式串 p，将其字符频率统计到 cntP 数组中。这个数组是固定不变的“目标”。

2. 一体化的滑动窗口遍历：

   • 与上一个版本先初始化窗口再滑动的两步法不同，此版本将窗口的初始化、扩张、校验和收缩整合在一个 for 循环中。
   • 循环由一个 right 指针驱动，从头到尾遍历主串 s。
   • 窗口扩张：在每次迭代中，首先将 right 指针指向的字符计入窗口频率数组 cntS。
   • 窗口形成与校验：通过 left = right - m + 1 计算出窗口的左边界。
     • if (left < 0) 这个条件用于处理窗口还未形成完整大小（长度为 m）的初始阶段。在窗口大小不足 m 时，只进行扩张，不进行比较和收缩。
     • 当 left >= 0 时，说明窗口已经达到了 m 的长度。此时，使用 Arrays.equals(cntP, cntS) 来比较两个频率数组。Arrays.equals 会逐一比较数组中的每个元素，如果所有元素都相等，则证明当前窗口内的子串是 p 的一个异位词，将其起始索引 left 加入结果列表。
   • 窗口收缩：在完成校验后（无论是否匹配），将 left 指针指向的字符从窗口中移除（即在 cntS 中将其频率减一），为下一次迭代做准备。这样，窗口就整体向右平移了一格。

3. 返回结果：

   • 循环结束后，返回包含所有起始索引的结果列表 ans。

这种一体化的实现方式代码更紧凑，逻辑流程非常清晰：每一步都“加一个右边的，（可能的话）比一下，再减一个左边的”。

完整代码

class Solution {
    /**
     * 在字符串 s 中查找 p 的所有异位词的起始索引。
     * 此版本使用数组进行频率统计，优化了性能。
     * @param s 主字符串 (假定只包含小写字母)
     * @param p 模式字符串 (假定只包含小写字母)
     * @return 一个包含所有匹配起始索引的列表
     */
    public List<Integer> findAnagrams(String s, String p) {
        // ans 用于存储结果，即所有异位词的起始索引
        List<Integer> ans = new ArrayList<>();
        // n 是主串 s 的长度，m 是模式串 p 的长度
        int n = s.length();
        int m = p.length();
        // 如果主串比模式串还短，直接返回空列表
        if (n < m) {
            return ans;
        }

        // cntS: 存储当前滑动窗口内子串的字符频率
        // cntP: 存储模式串 p 的字符频率
        // 使用大小为 26 的数组，因为题目隐含了输入为小写英文字母
        int[] cntS = new int[26];
        int[] cntP = new int[26];

        // 步骤 1: 统计模式串 p 中每个字符的出现次数
        for (char c : p.toCharArray()) {
            // 'c' - 'a' 将字符映射到 0-25 的索引
            cntP[c - 'a']++;
        }

        // 步骤 2: 滑动窗口遍历主串 s
        for (int right = 0; right < n; right++) {
            // a. 窗口扩张：将右边界字符加入窗口的频率统计中
            cntS[s.charAt(right) - 'a']++;
            
            // 计算当前窗口的左边界索引
            int left = right - m + 1;
            
            // 判断窗口是否已形成。当 left < 0 时，窗口大小不足 m，跳过比较和收缩步骤。
            if (left < 0) {
                continue;
            }
            
            // b. 窗口内校验：当窗口大小正好为 m 时，比较窗口和模式串的频率数组
            // Arrays.equals() 逐元素比较两个数组，如果完全相同则返回 true
            if (Arrays.equals(cntP, cntS)) {
                // 如果是异位词，将当前窗口的起始索引 left 加入结果列表
                ans.add(left);
            }
            
            // c. 窗口收缩：将即将移出窗口的左边界字符的频率减一
            cntS[s.charAt(left) - 'a']--;
        }

        // 返回最终的结果列表
        return ans;
    }
}

时空复杂度

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

1. 模式串频率统计：for (char c : p.toCharArray()) 循环遍历模式串 p 一次。设 p 的长度为 M，此步骤时间复杂度为 O(M)。
2. 滑动窗口遍历：for (int right = 0; right < n; right++) 循环遍历主串 s 一次。设 s 的长度为 N，此循环执行 N 次。
   • 在循环内部：
     • 数组的读写操作（cntS[...]++ 和 cntS[...]--）是 O(1) 的。
     • Arrays.equals(cntP, cntS) 操作需要比较两个数组中的所有元素。由于数组大小是固定的 26，所以比较的次数也是常数 26。因此，该操作的时间复杂度为 O(26)，即 O(1)。
   • 所以，整个循环的时间复杂度是 N 次 O(1) 操作，总计为 O(N)。

综合分析：
总时间复杂度 = 预处理 p 的时间 + 遍历 s 的时间 = O(M) + O(N) = O(N + M)。
由于通常 N 是远大于 M 的，所以有时也近似地称为 O(N)，但 O(N + M) 是更精确的表述。

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

1. 主要存储开销：算法使用了两个整型数组 cntS 和 cntP。
   • 每个数组的大小都是 26，这是一个固定的常数，不随输入字符串 s 和 p 的长度变化而变化。
   • k 在这里代表字符集的大小，即 26。
2. 其他变量：n, m, right, left 等变量占用的是常数空间 O(1)。
3. 结果列表：ans 列表用于存储输出，其空间不计入辅助空间复杂度。

综合分析：
算法所需的额外辅助空间主要由两个频率数组决定。由于数组大小是固定的，所以空间复杂度是 O(k)，其中 k=26。因为 k 是一个常数，所以也可以表述为 O(1)。这表示算法占用的额外内存是一个常数，非常高效。