滑动窗口的小小总结

题型概述和分析

滑动窗口问题通常会给出一长一短的两个字符串：s和t

核心目的是让你判断s中是否包含t

整体的思路如下：

初始化两个哈希表，need表示字符串t各个字符的个数，window表示当前窗口内各个所需字符的个数，用变量missingType表示当前窗口缺少的字符种类
用 left 和 right 两个指针形成左闭右开的一个窗口
在外层循环中，不断增加right，扩大窗口并更新window、missingType，直到窗口中的字符串符合要求
当窗口中的字符串符合要求时，进入内层循环：停止增加right，转而增加left以缩小窗口，每次缩小窗口都要更新window、missingType和“结果”
重复第2步和第3步，直到right到达s的尽头

在做题的时候，我们可以先把整个框架搭建起来，再去思考以下问题：

如何表示“窗口中的字符串符合要求” => 进入内层循环的条件
如何更新“结果” => 依据题目情况具体分析

下面来看3道例题

最小覆盖子串-LeetCode(76)

解题思路

什么时候“窗口中的字符串才符合要求？

显然，是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)

解题思路

什么时候“窗口中的字符串满足要求”？

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