跳至主要內容

字符串的排列：固定窗口大小的字符频次比较

老张2026/4/30大约 6 分钟

字符串的排列：固定窗口大小的字符频次比较

适读人群：Java 后端工程师、算法中阶学习者 | 阅读时长：约 16 分钟 | 难度：⭐⭐⭐

开篇故事

"字符串的排列"和"找到字符串中所有字母异位词"是孪生题目（567 和 438），只是前者问"是否存在"，后者问"所有位置在哪里"。把这两道题放在一起学，会有事半功倍的效果。

这类题目的核心问题是：如何快速判断一个固定大小的窗口内的字符频次，与目标字符串的频次是否相同？

有三种常见方式：

  1. 每次完整比较两个频次数组（O(26)）
  2. 用一个 diff 计数器维护"有多少字符的频次不匹配"，每次滑动窗口时 O(1) 更新
  3. 用 HashMap 维护差值

今天把三种方式都实现一遍，尤其是方式 2，是最常见的高效写法。

一、题目解析

题目（LeetCode 567）： 给你两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。如果包含，返回 true；否则，返回 false。

示例：

  • s1 = "ab"，s2 = "eidbaooo"，输出：true（s2 包含 s1 的排列 "ba"）
  • s1 = "ab"，s2 = "eidboaoo"，输出：false

核心思路： s2 的某个子串是 s1 的排列，等价于该子串与 s1 的字符频次完全相同。使用固定大小为 s1.length() 的滑动窗口。

二、解法一：暴力 + 排序 O(n * m log m)

public class Solution1 {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;
        char[] sorted1 = s1.toCharArray();
        Arrays.sort(sorted1);
        String sortedS1 = new String(sorted1);

        int m = s1.length();
        for (int i = 0; i <= s2.length() - m; i++) {
            char[] window = s2.substring(i, i + m).toCharArray();
            Arrays.sort(window);
            if (new String(window).equals(sortedS1)) return true;
        }
        return false;
    }
}

复杂度分析

  • 时间复杂度：O(n * m log m)。n 个窗口位置，每次排序 O(m log m)。
  • 空间复杂度：O(m)。

三、解法二：固定窗口 + 频次数组比较 O(26n)

public class Solution2 {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;
        int m = s1.length(), n = s2.length();

        int[] freq1 = new int[26];
        int[] freq2 = new int[26];

        // 初始化第一个窗口
        for (int i = 0; i < m; i++) {
            freq1[s1.charAt(i) - 'a']++;
            freq2[s2.charAt(i) - 'a']++;
        }

        if (Arrays.equals(freq1, freq2)) return true;

        // 滑动窗口
        for (int right = m; right < n; right++) {
            freq2[s2.charAt(right) - 'a']++;           // 纳入右端
            freq2[s2.charAt(right - m) - 'a']--;        // 移出左端
            if (Arrays.equals(freq1, freq2)) return true;
        }
        return false;
    }
}

复杂度分析

  • 时间复杂度：O(26n)，即 O(n)。每步 O(26) 比较数组。
  • 空间复杂度：O(1)（两个大小 26 的数组）。

四、解法三最优：diff 计数器，O(1) 比较

核心思路

维护一个整数 diff，表示"当前窗口与 s1 频次不匹配的字符数量"。初始化时计算第一个窗口的 diff。滑动窗口时，每次只更新涉及的两个字符（新加入的 right 字符和移出的 left 字符）对 diff 的贡献。diff == 0 则找到了答案。

更新 diff 的逻辑：

当纳入新字符 c（freq2[c]++）：

  • 若 freq2[c] 从 freq1[c] 变成了 freq1[c]+1（即 freq2[c]-1 == freq1[c]，现在不等了），diff++。
  • 若 freq2[c] 从 freq1[c]-1 变成了 freq1[c]（即现在相等了），diff--。

当移出旧字符 c（freq2[c]--）：

  • 若 freq2[c] 从 freq1[c] 变成了 freq1[c]-1（不等了），diff++。
  • 若 freq2[c] 从 freq1[c]+1 变成了 freq1[c]（相等了），diff--。

Mermaid 图

完整代码

public class Solution3 {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) return false;

        int m = s1.length(), n = s2.length();
        int[] freq = new int[26];  // freq[c] = freq1[c] - freq2[c]，目标是全0

        // 初始化：先计算 s1 的频次
        for (char c : s1.toCharArray()) {
            freq[c - 'a']++;
        }
        // 减去第一个窗口的频次
        for (int i = 0; i < m; i++) {
            freq[s2.charAt(i) - 'a']--;
        }

        // 计算初始 diff（不等于0的字符数）
        int diff = 0;
        for (int f : freq) {
            if (f != 0) diff++;
        }
        if (diff == 0) return true;

        // 滑动窗口
        for (int right = m; right < n; right++) {
            int rightChar = s2.charAt(right) - 'a';
            int leftChar = s2.charAt(right - m) - 'a';

            // 纳入 right 处字符（freq[rightChar]--，因为 freq = freq1 - freq2）
            freq[rightChar]--;
            if (freq[rightChar] == 0) diff--;        // 恰好平衡了
            else if (freq[rightChar] == -1) diff++;  // 从平衡变为过多

            // 移出 left 处字符（freq[leftChar]++）
            freq[leftChar]++;
            if (freq[leftChar] == 0) diff--;         // 恰好平衡了
            else if (freq[leftChar] == 1) diff++;    // 从平衡变为过少

            if (diff == 0) return true;
        }

        return false;
    }

    public static void main(String[] args) {
        Solution3 sol = new Solution3();
        System.out.println(sol.checkInclusion("ab", "eidbaooo")); // true
        System.out.println(sol.checkInclusion("ab", "eidboaoo")); // false
        System.out.println(sol.checkInclusion("adc", "dcda"));    // true
        System.out.println(sol.checkInclusion("a", "a"));         // true
    }
}

复杂度分析

  • 时间复杂度：O(n + m)。初始化 O(m)，滑动 O(n)，每步 O(1)。
  • 空间复杂度：O(1)（26 个字母）。

五、举一反三

题号题目区别
438找到字符串中所有字母异位词返回所有满足条件的起始位置
76最小覆盖子串窗口不固定大小，需要包含所有字符
242有效的字母异位词判断两个字符串是否互为异位词

438 的完整代码（在 567 基础上增加收集功能）：

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    if (p.length() > s.length()) return result;
    // 与 567 的代码几乎完全一样，只需把 return true 改为 result.add(right - p.length() + 1)
    // 最终返回 result
    // ... (代码见下一篇 article-578)
    return result;
}

六、踩坑实录

坑一：diff 更新时条件判断出错

diff 的更新逻辑是：操作完 freq[c] 后，判断新的值是否为 0（刚刚平衡）或刚好从 0 变成 ±1（刚刚失衡）。很多人把判断条件写错，比如应该是 freq[c] == 0 时 diff--，写成了 freq[c] == 1 时 diff--。要仔细理清每个操作前后的变化方向。

坑二：把 freq 定义为 freq1 - freq2 还是 freq2 - freq1

两种方向都可以，但要自洽。我在代码里用的是 freq = freq1 - freq2（s1 的频次减去 s2 当前窗口的频次），所以纳入 s2 的新字符时 freq[c]--，移出时 freq[c]++。如果反过来定义，所有操作方向都要反过来。

坑三：s1 比 s2 长的情况

s1.length() > s2.length() 时，s2 里不可能有 s1 的排列，直接返回 false。这个特判要放在最前面，否则后面的初始化循环会越界。

坑四：初始化第一个窗口后就检查一次

在初始化完第一个窗口并计算 diff 后，立即判断 diff == 0，可能第一个窗口就是答案。不要忘记这个初始检查，直接从 right = m 开始滑动会漏掉第一个窗口的情况。（当然，也可以在滑动循环里统一处理，只要逻辑一致即可。）

七、总结

固定窗口大小的字符异位词判断，核心是高效维护窗口内的字符频次与目标频次的"差距"。diff 计数器把每次 O(26) 的数组比较优化为 O(1) 的常数操作，是这道题的最优解法。

这种用"差异计数"替代"完整比较"的思路，在字符串的窗口问题里非常通用，务必熟练掌握。

编辑此页
最近更新:
贡献者: xiaozhangge