碎碎念?

　　大家好，我是潘小安！一个永远在减肥路上的前端er? ！

　　在北京时间的 2022 年 3 月 19 日，我找到了一个 2021 年 7 月 19 日创建的滑动窗口刻意练习的思路草稿，借着这次新年 flag 和最近的训练营刷题计划，捡起来写写。

　偶然看到一本书中说的，不怕你的计划没有按时完成，怕的是你沉浸在因计划没完成而产生的悔恨和自我否定中，然后就再也没有新的计划。以前总会对自己立下的 flag 未能实现耿耿于怀，之后逐渐把这件事看开了。接受自己写了计划未能如期执行的瑕疵，一点点的前进，在路上就是好的。

上菜 ?

直接上题：

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

输入： s = "ADOBECODEBANC", t = "ABC"
输出： "BANC"
复制代码

输入： s = "a", t = "a"
输出： "a"
复制代码

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
复制代码

观其色闻其味 ?

看完题目就去写代码，就中了算法题的圈套了。拿到题目，我们第一时间是要进行　“观其色闻其味”。换句话说是要理清楚逻辑，看看这道题目到底是要考察我们哪部分知识点。题目中我们是要寻找包含 t 目标串的最短子串，拆分开来就是我们要解决两个问题：

怎么去识别包含
怎么确定最短

接下来我们就从这两个子问题，来寻找这道题的解题方法。

如何识别子串包含目标串？

如果给你两个字符串 s 和 t，让你判断 s 是否包含 t。你会怎么去想？
我的第一个想法就是先把 t 中所有的字符遍历，保存在一个对象 tmap 中，并统计数量。

var generateMap = function (t) {
    let tmap = {}
    for (let key of t) {
        if (tmap[key] != undefined) {
            tmap[key]++
        } else {
            tmap[key] = 1
        }
    }
    return tmap
}
复制代码

之后遍历 s 子串，如果检查到字符存在于 tmap 中，则对该字符数量减 1，当对象中所有的值都小于等于 0 的时候，说明 s 完全包含了 t。

var iscontained = function (tmap) {
    let values = Object.values(tmap)
    return values.filter(item => item <= 0).length == values.length
}
复制代码

写到这里，似乎仿佛好像暂时解决了这个问题。但是我们什么时候调用这个方法去做判断呢？每一次命中的时候吗？
这显然是不够有效率的，会浪费很多次无效的判断。

有没有更好的，更简单的方法来判断呢？答案是有！我们引入一个新的变量 typenum 来表示 tmap 中所有字母的种类：

let typenum=Object.keys(tmap).length
复制代码

遍历 s 时，每次命中后我们除了把在 tmap 中对应的值减 1 之外，我们还可以判断减 1 之后该值是不是为 0，如果为0，则吧 typenum 减 1。

比如当 s 为 “ACBBCD”,t 为 “ABB”的时候，我们使用 t 建立的对象如下，typenum 为 2：

{
    A:1,
    B:2
}
复制代码

我们遍历 s 到 "A" 的时候，对象中的 "A" 为 0，这时候相当于 s 已经覆盖完成了 t 中的 "A",这时候我们把 typenum 也减少 1，当遍历到最后的 B 的时候，typenum 为零，这个时候子串为 "ACBB"。
结论就是我们用一个变量 typenum，结合 tmap 来判断子串是否覆盖，而不用 iscontained　这个方法，优点就是引入 typenum 变量后，既解决了判断时机的问题，又解决了判断方法的问题。

如何确定最短

我们用这道题的第一个例子来辅助我们去理解滑动窗口的解题逻辑和思路历程。我们直观看过去的话，可以一眼就看出最短的符合要求的字串是"BANC",但是程序是如何去判断的？肯定是找到所有符合要求，也就是所有包含 t 的 s 的子串，然后比较之后拿到长度最短的。于是我们的问题就变成了：如何拿到所有符合条件的子串？

暴力双循环

简单观察可以发现，只要是符合最短子串的，首位两个元素一定是 t 中的元素。所以使用双循环遍历的时候，可以过滤掉很多非 t 中的元素，可以很大程度上减少多余的遍历。

结合这一点，我们可以在第一层循环中确认起点，在第二层循环中，使用上面提到的检查包含的方法确认终点，最后可以得出正确的结果。不出意外的话，当你写完这段代码点击提交的时候会得到以下结果：

（对暴力解法感兴趣的同学可以私聊一起讨论）

怎么办？接下来要介绍的是我们本文的主题，滑动窗口。

滑动窗口

从题目中我们可以初窥端倪，提到了”最小”，”涵盖”等字样，我们可以尝试使用滑动窗口来解决这类问题（净搁这说废话，自己标题都写了是滑动窗口的刻意练习）。那滑动窗口是什么？
滑动窗口，顾名思义就是一个窗子，但是这个窗子的左右边框是可以移动的，左右边框也就是我们常说的左右指针。一般使用滑动窗口的关键在于我们需要确认几个点：

右边的窗口什么时候动？
左边的窗口什么时候动？
处理窗口中的值

搞清楚这几个点，滑动窗口的问题其实就非常的简单，接下来我们结合这道题的第一个实例，来探索一下滑动窗口的魅力。

输入： s = "ADOBECODEBANC", t = "ABC"
输出： "BANC"
复制代码

右边的窗口什么时候动

在本题中，右窗口向右滑动的时机是窗内的 s 子串不包含 t。

初始化的时候，我们的窗口大小为 0，换句话说就是左指针 l 和有指针 r 都在初始位置 0。我们的框内只有一个值，就是 s[0]。

这个时候就是需要我们右边的窗口动一动，直到窗内的子串满足条件，包含了 “ABC”。

我们截取 l 到 r 之间的子串，就得到了我们第一个符合条件的子串，我们可以把它暂时保存起来。接下来呢？接下来要看左边的窗口的表演了。

左边的窗口什么时候动

左边的窗口什么时候动？在窗口内的子串已经符合条件的情况下，移动左边窗口，对已有的子串进行压缩，直到获得最小的子串。于是我们移动一下左窗口 l，得到下面的情况：

接下来呢？我们现在 l 和 r 之间的子串不满足条件了，我们当然要开始移动 r 这个窗边咯。反复执行这个过程，直到 r 到了 s 字符的末尾才结束。

处理窗口中的值

这里有个细节问题值得我们讨论，就是什么时候我们做截取字符串并且比较找最小值？在整个指针移动过程中，每次可能的最短子串应该是在 l 指针，也就是左边的窗口进行移动，从符合条件的子串到不符合条件的子串的这一步，我们可以拿到当前 r 情况下符合条件的最短子串。大家可以自己手敲代码去理一理思路。

下筷子 ?

我们根据这个思路开始写代码:

//获取目标值的每个字符的数量，用对象保存
var generateMap = function (t) {
    let tmap = {}
    for (let key of t) {
        if (tmap[key] != undefined) {
            tmap[key]++
        } else {
            tmap[key] = 1
        }
    }
    return tmap
}
var minWindow = function (s, t) {
    //一些边界条件
    if (s.length < t.length) {
        return ''
    }
    //一些边界条件
    if (s.indexOf(t) > -1) {
        return t
    }
    let tmap = generateMap(t)
    let minstr = ''
    let l = 0
    let r = 0
    let typenum = Object.keys(tmap).length
    while (r < s.length) {
        //确认起点
        if (tmap[s[r]] != undefined) {
            tmap[s[r]]--
            //有一种字符被全覆盖了
            if (tmap[s[r]] == 0) {
                typenum--
            }
            //全覆盖后进入收缩过程
            while (typenum == 0) {
                //左指针遇到了 map 中的值，且该值会使得 typenum 增加，跳出 l 移动的循环，回到 r 移动循环
                if (tmap[s[l]] != undefined) {
                    tmap[s[l]]++
                    if (tmap[s[l]] == 1) {
                        //截取字符串
                        let newminstr = s.substring(l, r + 1)
                        //比较拿到最短的那个
                        minstr = (!minstr || newminstr.length <= minstr.length) ? newminstr : minstr
                        typenum++
                    }
                }
                l++
            }
        }
        r++
    }
    return minstr
};

复制代码

小声BB

　　这道题在力扣上标注的是困难程度，自习分析下来发现自己是可以解决的。随着学习的深入，发现自己对算法的恐惧感逐渐减少，也验证了那句话，未知的才是恐惧的。

　　最近在参加一个为期 21 天的打卡训练营，每天监督大家和自己完成开始时候定下的日常任务，其中就包括每日一道算法题。昨天遇到了这道滑动窗口问题的时候，猛然想起掘金草稿箱里有一篇当时想写，现在已经长灰了的《刻意练习之滑动窗口》，正好这道题目又足够经典且有一定的难度。于是花了点时间把当年立的 flag 来完成一下下，虽说迟了些，但正如我在前言中提到的一样，在路上，就是好的，就目前情况来说，新年的 flag 还在。

　　最近还在看一本关于营销的书，还有一本《明朝的那些事》，目前看到了重八同学把宰相制度废除那部分，接下来的故事应该会更精彩。

　　最近在期待海贼王的最新一话，想看看觉醒后的路飞同学到底有多强。想看下陪伴很久的最终谜团是否会比出乎意料更加出乎意料，还是说早已经被海米们猜中落了俗套。

　　最后贴一张在小破站看到的一五档手作，来自这里，侵删！