字符串的排列怎么用固定长度滑动窗口判断？如何比较字符计数？

简化版

判断 s2 是否包含 s1 的排列，本质是看 s2 是否存在一个长度等于 s1.length() 的子串，字符计数和 s1 完全相同。维护固定长度窗口的字符频次，右边加入新字符，窗口超过长度就从左边移出旧字符；计数匹配就返回 true。

详细版

排列不关心顺序，只关心每个字符出现次数。因此先统计 s1 的频次，再在 s2 上滑动长度为 m 的窗口。每移动一步，只更新两个字符：新进入窗口的字符 +1，离开窗口的字符 -1。若窗口计数和目标计数相等，说明当前窗口是 s1 的某个排列。

例如 s1="ab", s2="eidbaooo"，窗口长度为 2。当窗口滑到 "ba" 时，a 和 b 的计数都为 1，匹配目标，返回 true。若 s1 比 s2 长，直接 false。

优化比较方式有两种：每次比较 26 个计数数组，复杂度 O(26n)，常数可接受；或维护 matches 表示有多少字符的计数已经相等，做到更细致的 O(n)。

完整版教学

一、为什么排列可以转成计数

排列只改变字符顺序，不改变字符种类和出现次数。"abc" 的排列可以是 "bca"、"cab"，但它们都有 a:1,b:1,c:1。所以判断某个窗口是不是排列，不需要排序，也不需要枚举所有排列，只要比较计数。

如果 s1 长度是 10，排列数量最多是 10! = 3628800，枚举完全不可取。计数数组把判断压缩成 26 个小整数的比较，这就是固定窗口的根本价值。

s1 = "aab"
目标计数: a=2, b=1
窗口 "aba": a=2, b=1 -> 匹配
窗口 "abb": a=1, b=2 -> 不匹配

记忆钩子：排列题先问“顺序重要吗”，不重要就优先想频次表。

二、为什么窗口长度固定

目标排列必须和 s1 长度相同。长度短了字符不够，长度长了字符多余，所以窗口大小固定为 m = s1.length()。固定窗口比可变窗口简单：每次右边加入一个字符后，如果窗口超过 m，就移出左边一个字符。

这保证每一步检查的都是“候选排列长度”。以 s2="eidbaooo"、m=2 为例，候选窗口依次是 "ei"、"id"、"db"、"ba"、"ao"、"oo"、"oo"。

right 加入 s2[right]
if 窗口长度 > m:
    移出 s2[left], left++
if 窗口长度 == m 且计数相等:
    return true

三、计数数组比较的写法

最直观写法是两个长度 26 的数组：need 保存 s1，win 保存当前窗口。每次窗口长度达到 m，就比较两个数组。由于 26 是常数，复杂度仍可视为 O(n)。

boolean checkInclusion(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    if (m > n) return false;
    int[] need = new int[26], win = new int[26];
    for (int i = 0; i < m; i++) need[s1.charAt(i) - 'a']++;
    int left = 0;
    for (int right = 0; right < n; right++) {
        win[s2.charAt(right) - 'a']++;
        if (right - left + 1 > m) {
            win[s2.charAt(left) - 'a']--;
            left++;
        }
        if (right - left + 1 == m && Arrays.equals(need, win)) return true;
    }
    return false;
}

这段代码的优点是稳定，不容易写错。面试如果时间紧，优先写这个版本。

四、matches 优化如何理解

如果不想每次比较 26 个位置，可以维护 matches：表示有多少个字符满足 need[c] == win[c]。当某个字符计数变化时，只需要更新它对 matches 的贡献。

例如进入字符 b 前，need[b]=1, win[b]=0，不匹配；进入后 win[b]=1，匹配数 +1。离开字符 a 前可能匹配，离开后若不匹配，匹配数 -1。

更新场景	操作前	操作后	matches 变化
加入字符后刚好相等	不匹配	匹配	+1
加入字符后超过需要	匹配	不匹配	-1
移出字符后刚好相等	不匹配	匹配	+1
移出字符后低于需要	匹配	不匹配	-1

五、带数字手推

s1="ab"，s2="eidbaooo"。目标计数是 a=1,b=1，窗口长度为 2。

窗口 "ei": e=1,i=1，不匹配
窗口 "id": i=1,d=1，不匹配
窗口 "db": d=1,b=1，不匹配
窗口 "ba": b=1,a=1，匹配 -> true

每一步只改两个计数：进入右端字符，必要时移出左端字符。固定窗口题最怕把窗口长度控制和计数更新顺序写乱，所以手推时要同时记录 left/right 和窗口内容。

六、常见误区与追问

误区：枚举 s1 的所有排列再到 s2 里查找。 排列数量阶乘级，长度稍大就不可行。
误区：把子序列当成子串。 题目要求连续窗口，不能跳着选字符。
误区：窗口超过 m 时忘记移出左端字符。 计数会包含多余字符，导致误判。
追问：如果字符集不止小写字母怎么办？ 用哈希表计数，或按题目字符集扩大数组。
追问：为什么比较数组仍是 O(n)？ 因为每次比较 26 个固定位置，26 是常数。
追问：这题和异位词分组有什么关系？ 都利用“频次决定排列等价类”，但一个是在滑动窗口中找匹配，一个是在集合中分组。

七、复杂度与边界

数组比较版本时间是 O(26n)，通常写作 O(n)，空间 O(1)。matches 版本也是 O(n)，但实现复杂度更高，面试除非被追问优化，否则不必强行写。

边界包括：s1 比 s2 长直接 false；s1 为空时不同平台定义可能不同，刷题通常长度至少为 1；重复字符必须按次数比较，不能只用集合。

s1 = "aabc"
窗口 "abca": 匹配
窗口 "abcd": 不匹配，因为 a 少 1 个，d 多 1 个

八、加强记忆

这题的主线是“排列等价于字符频次相同”。先锁定固定窗口长度 m，再维护窗口频次，最后比较目标频次。写代码时按“右进、超长左出、长度够就检查”的节奏走，重复字符和边界就不容易漏。

简化版

详细版