💡 题目简介
LeetCode 567：判断字符串 s2 中是否包含 s1 的排列。
- 输入：
s1 = "ab",s2 = "eidbaooo" - 输出：
true（因为 "ba" 是s1的一个排列，出现在了s2中）
🚧 初始暴力解法
第一版思路是暴力枚举 s2 中所有长度为 s1.length 的子串，然后和 s1 的频率 Map 逐一对比。
function getCharFrequencyMap(s) {
const map = new Map()
for (const ch of s) {
map.set(ch, (map.get(ch) || 0) + 1)
}
return map
}
function isSameFrequencyMap(map1, map2) {
if (map1.size !== map2.size) return false
for (const [key, val] of map1.entries()) {
if (map2.get(key) !== val) return false
}
return true
}
var checkInclusion = function(s1, s2) {
const map = getCharFrequencyMap(s1)
let left = 0, right = s1.length - 1
while (right < s2.length) {
const tmpMap = getCharFrequencyMap(s2.slice(left, right + 1))
if (isSameFrequencyMap(map, tmpMap)) return true
left++
right++
}
return false
}
- ✅ 能通过样例
- ❌ 子串每次都重新建
Map，性能瓶颈在于重复统计
✅ 优化：滑动窗口 + Map
借助滑动窗口的思想，用一个 Map window 记录当前窗口内字符频次，并维护一个 valid 变量，表示窗口内频次完全匹配的字符数。
var checkInclusion = function(s1, s2) {
const map = getCharFrequencyMap(s1)
const window = new Map()
let left = 0, right = 0, valid = 0
while (right < s2.length) {
const ch = s2[right]
right++
if (map.has(ch)) {
window.set(ch, (window.get(ch) || 0) + 1)
if (window.get(ch) === map.get(ch)) {
valid++
}
}
while (right - left >= s1.length) {
if (valid === map.size) return true
const del = s2[left]
left++
if (map.has(del)) {
if (window.get(del) === map.get(del)) {
valid--
}
window.set(del, window.get(del) - 1)
}
}
}
return false
}
🔍 对比优化点：
| 比较项 | 暴力解 | 滑动窗口 |
|---|---|---|
| 子串频次统计 | 每次重新统计 | 滑动更新，O(1) 复杂度 |
| 总体时间复杂度 | O(n × m) | O(n) |
| 实际表现 | 小样本可过 | 大样本稳定高效 |
🧠 总结
- 对于子串匹配问题，滑动窗口 + 频次统计 + 有效计数 是性能利器。
- 一定要养成“避免重复计算”的优化思维。
- 本题使用
Map实现频次统计，对所有字符集都适用，也可以替换为定长数组优化为O(26)。
如果你也在刷题中遇到性能问题，不妨静下心来思考是否可以引入状态缓存或滑动窗口技巧 😉。