问题描述给定两个字符串s1和s2判断s2是否包含s1的某个排列作为子串。示例输入s1 ab,s2 eidbaooo→ 输出true包含ba输入s1 ab,s2 eidboaoo→ 输出false方法一暴力枚举 模拟TLE思路1枚举s2中所有长度为s1.size()的子串对每个子串和s1分别排序后比较是否相等。bool checkInclusion(string s1, string s2) { sort(s1.begin(), s1.end()); for (int i 0; i s1.size() s2.size(); i) { string sub s2.substr(i, s1.size()); sort(sub.begin(), sub.end()); if (sub s1) return true; } return false; }复杂度O(n·m log m)其中 n |s2|m |s1|。当 n 10⁴ 时必然超时。问题每次窗口滑动都重新排序浪费了大量重复计算。思路2位置标记法试图用一个标记数组a来记录s2中哪些位置可以作为匹配起点然后在内层循环中逐位打标记通过标记是否全部命中来判断当前窗口是否为s1的排列。vectorint a(s2.size() s1.size()); // 初始化把前 s1.size() 个位置标记为 1可作起点 for (int j 0; j s1.size(); j) a[j] 1; for (int i 0; i s2.size(); i) { if (a[i] 1 (i s1.size()) s2.size()) { a[i]; // 标记起点已匹配 int flag 1; for (int j 1; j s1.size(); j) { if (a[j i] ! 2 a[j i] 1) { a[j i]; // 标记窗口内其他位置已匹配 } else { flag 0; break; } } // 重置窗口内的标记 for (int j 0; j s1.size(); j) a[j i] 1; if (flag 1) ans 1; } }方法二位置标记法错误思路错误尝试用一个数组a标记s2中哪些位置可作为起点然后在内层循环中逐位打标记试图通过标记是否全部命中来判断匹配。vectorint a(s2.size()); for (int j 0; j s1.size(); j) a[j] 1; // ... 后续通过修改 a[i] 的值来标记匹配为什么错只标记位置不比较字符a数组只记录了第 i 个位置是否被访问完全没有携带字符信息。对于s1 abs2 aa也会被误判为匹配。状态被污染后无法恢复内层循环把a[i]从 1 改成 2 后重置时容易遗漏导致后续判断基于错误数据。本质问题排列是一个字符频次问题不是位置覆盖问题。结论方向错误无论怎么修补都无法通过。方法三滑动窗口 字符频率统计正解核心洞察排列不改变字符的出现次数。因此问题等价于在s2中是否存在一个长度为|s1|的窗口其字符频率分布与s1完全一致。算法设计用两个长度 26 的数组count1和count2分别统计s1和s2当前窗口的字符频率。初始化第一个窗口count2统计s2[0..|s1|-1]。窗口每次右移一位右侧加入新字符count2[s2[i]]左侧移除旧字符count2[s2[i - |s1|]]--每移动一次比较count1 count2。代码实现class Solution { public: bool checkInclusion(string s1, string s2) { int n1 s1.size(), n2 s2.size(); if (n1 n2) return false; vectorint count1(26, 0), count2(26, 0); // 初始化 s1 和 s2 的第一个窗口 for (int i 0; i n1; i) { count1[s1[i] - a]; count2[s2[i] - a]; } if (count1 count2) return true; // 滑动窗口 for (int i n1; i n2; i) { count2[s2[i] - a]; // 右进 count2[s2[i - n1] - a]--; // 左出 if (count1 count2) return true; } return false; } };复杂度分析指标值时间复杂度O(n m)n |s2|m |s1|空间复杂度O(1)两个固定大小 26 的数组每个字符最多被加入和移除各一次且vectorint的比较是常数级26 次。方法总结方法核心思路复杂度是否可行暴力排序枚举所有子串排序比较O(n·m log m)❌ 超时位置标记标记位置代替字符比较—❌ 逻辑错误滑动窗口 频率统计比较字符频次分布O(n m)✅ 最优