题型概述和分析
滑动窗口问题通常会给出一长一短的两个字符串：s和t
核心目的是让你判断s中是否包含t
整体的思路如下：
初始化两个哈希表，need表示字符串t各个字符的个数，window表示当前窗口内各个所需字符的个数，用变量missingType表示当前窗口缺少的字符种类
用 left 和 right 两个指针形成左闭右开的一个窗口
在外层循环中，不断增加right，扩大窗口并更新window、missingType，直到窗口中的字符串符合要求
当窗口中的字符串符合要求时，进入内层循环：停止增加right，转而增加left以缩小窗口，每次缩小窗口都要更新window、missingType和“结果”
重复第2步和第3步，直到right到达s的尽头
在做题的时候，我们可以先把整个框架搭建起来，再去思考以下问题：
- 如何表示“窗口中的字符串符合要求” => 进入内层循环的条件
- 如何更新“结果” => 依据题目情况具体分析
下面来看3道例题
最小覆盖子串-LeetCode(76)
image
解题思路
什么时候“窗口中的字符串才符合要求？
显然，是missingType等于0的时候：此时窗口中的字符串涵盖了t的所有字符
什么时候更新“结果”？
题目要求的是最小(即长度最短)的子串：我们可以用 start + len 来记录上一个找到的最小子串，当 right- left 小于len时，就可以更新start和len了
看代码：
var minWindow = function(s, t) {
var missingType = 0
const need = {}
const window={}
for(let i=0;i<t.length;i++){
if(need[t[i]]){
need[t[i]]++
}else{
missingType++
need[t[i]]=1
}
}
var left = 0
var right = 0
var start = 0
var len = s.length+1
while(right<s.length){
let c = s[right]
right++
if(need[c] !== undefined){
if(window[c]!==undefined){
window[c]++
}else{
window[c]=1
}
if(window[c]===need[c]){
missingType--
}
}
while(missingType === 0){
if(right-left<len){
start = left
len = right-left
}
let d = s[left]
left++
if(need[d]!==undefined && window[d]!==undefined){
if(window[d]===need[d]){
missingType++
}
window[d]--
}
}
}
return len === s.length+1 ? "" : s.substr(start,len)
};
字符串的排列-LeetCode(567)
image
解题思路
什么时候“窗口中的字符串满足要求”？
s1的排列意味着，我们要找的字符串长度必须与s1相同，也就是说，left和right的差值每次来到s1.length，就进入内层循环
什么时候更新”结果“？
题目并没有要求我们记录 符合要求的字符串，因此，当missingType=0的时候，就可以直接返回true了
看代码：
var checkInclusion = function(s1, s2) {
const need = {}
const window = {}
for(let i=0;i<s1.length;i++){
if(need[s1[i]]!==undefined){
need[s1[i]]++
}else{
need[s1[i]]=1
}
}
var left=0
var right=0
var valid = 0
var missingType = Object.keys(need).length
while(right<s2.length){
let c = s2[right]
right++
if(need[c]!==undefined){
if(window[c]!==undefined){
window[c]++
}else{
window[c]=1
}
if(window[c] === need[c]){
missingType--
}
}
while(right-left===s1.length){
if(missingType===0){
return true
}
let d = s2[left]
left++
if(need[d]!==undefined && window[d] !==undefined){
if(window[d] === need[d]){
missingType++
}
window[d]--
}
}
}
return false
};
总结
通过上面两道题，我们不难发现整体的代码框架是非常类似的：
- 初始化2个哈希表need和window，初始化变量missingType
- 用left和right两个指针形成左闭右开的窗口
- 在外层循环中，不断增加right，扩大窗口并更新window、missingType
- 当窗口中的字符串符合要求时，进入内层循环：停止增加right，转而增加left以缩小窗口，每次缩小窗口都要更新window、missingType和“结果”
- 重复第2步和第3步，直到right到达s的尽头
除此之外，还有一些细节需要注意：
- 扩大窗口与缩小窗口时，更新window和missingType的动作必须是完全对称的
- 谨慎编写window和missingType的更新动作，对某一个特定字符c，当前仅当window[c]等于need[d]时，才更新missingType
