LeetCode 904 水果成篮
题目链接：
题意解析：
本题是同向双指针中滑动窗口解法的应用，题意为给定 fruits 数组，每种数字代表一种水果，拥有两个篮子，每个篮子只能放一种采摘水果，要求采摘必须连续，求可以收集水果的最大数目。抽象一下题意可以表述为在给定的 int 类型的数组中，找到该数组的最长连续子数组，但是要求子数组内至多两种数字。
思路：
-
暴力解法：暴力的一个想法就是一层 for 循环控制采摘点的起始位置，因为题目要求一旦开始采摘就不能停下来（连续性），所以还需要一层 for 循环控制采摘点的结束位置，结束的条件就是收集了两种以上的水果。结果自然是一个 O(n^2) 的时间复杂度。
-
双指针：这里我们可以尝试使用一个 for 循环完成滑动窗口的动态扩充与缩减，需要用到快慢指针。快指针只负责向右扩充滑动窗口大小，慢指针只负责向右缩减滑动窗口大小。这里慢指针缩减窗口是需要一定的条件的，而快指针扩充窗口的条件却相对而言没有那么苛刻，因此考虑将快指针 fast 放入 for 循环借以控制移动，每次快指针移动就将新采摘的水果放入篮子 Map 中，数量++。接下来就是慢指针缩减窗口的条件，那就是当水果种类数量大于 2 时（map.size() > 2）就需要进入移动慢指针的环节了，而且因为考虑需要多次动态缩减，所以使用 while 循环控制。这里就采取与扩充相反的操作，把慢指针 slow 所到处的水果都踢出篮子 Map，数量--，而且一旦发现某个水果数量为 0 了（map.get(fruits[slow]) == 0）就把这个水果种类也彻底从 Map 中铲除掉（相当于 size--），维护动态窗口的合法性，避免陷入死循环。那在缩减窗口的 while 逻辑之后就是实时更新滑动窗口的历史最大长度（收集水果的最大数目），此刻的窗口一定是合法的。
总结：
- 快指针是导致滑动窗口合法性丧失的罪魁祸首
- 慢指针是使得滑动窗口重新合乎条件的帮手
- 快慢指针共同维护一个有条件的滑动窗口
LeetCode 76 最小覆盖子串
题目链接：
题意解析：
本题依旧是滑动窗口的应用，题意为给定两个字符串 s 和 t，要求返回 s 的一个最长子串，但要求这个子串包含 t 中每一个字符（包含关系即可，顺序无要求，不是每一种字符，因此需要考虑每种字符的数量也要一致）。
思路：
-
**暴力解法：**一层 for 循环控制 s 字符串的子串的起点，另一层 for 循环控制终点，在维护子串合法性的前提下，实时更新子串为最大长度。
-
滑动窗口：快指针 right 负责扩充窗口长度，for 循环中不断向右遍历，慢指针 left 负责缩减窗口长度，while 循环控制窗口非法性，循环内尝试更新 ansLeft 和 ansRight 保证最终窗口尽可能地长。前置操作设置两个长度为 128 的数组哈希 cntS 和 cntT，分别记录字符串 s 的子串窗口和字符串 t 中每种字符的数量。while 循环条件是由一个自定义方法 isCovered 负责判断，这个条件存在的根本原因是当当前窗口无法覆盖字符串 t 的所有字符时，为了通过慢指针循环移动使得窗口重新合法。而之前的数组哈希就是在此时派上用场了，isCovered 方法里面本质上就是遍历窗口和字符串 t 的每个字符，比较数量，一旦发现窗口中有某个字符数量小于字符串 t 中的某个字符，那就说明覆盖条件无法达成直接 return false，快指针继续遍历字符串 s，扩大窗口，让窗口重新覆盖字符串 t。如果覆盖条件达成，则继续 while 循环，慢指针右移，窗口中字符不断减少，试图'破坏'覆盖条件。
-
**滑动窗口（优化版）：**第二种方法的缺点在于每次 while 循环条件都要花费 O(52) 的时间去检查是否覆盖（isCovered 方法中 26 个英文字母大小写一共遍历 52 次），可以将该判断环节优化至 O(1)。**关键在于先将 cntS 和 cntT 都删去，只需要维护一个相同长度的 cnt 数组哈希即可，而 cnt[x] = cntT[x] - cntS[x]，即字符串 t 中字符 x 的数量比窗口中字符 x 的数量多多少。另一个关键变量 less 意为此时窗口有 less 种字母数量小于字符串 t 中对应字母数量。**这样一来 while 条件就可以写为 less == 0，即窗口中每种字母数量都大于等于 t 中对应字母数量，即达成所谓的覆盖。这样一来我们的重心就可以放在如何维护这个 less 变量了。一开始遍历字符串 t 的字符数组，有几种字符，less 就++几次，当然每个字符 c 对应的 cnt[c] 还是照常++。而在 for 循环中每次移动右指针 right 时，随着窗口内字符增多 cnt[array[right]] 就需要对应--，自减过后需要检查一下该字符的 cnt 值，如果重新为 0，就说明对于当前字符 array[right]，窗口和字符串 t 中各自数量是相同的了，达成局部覆盖，less 就可以--了。一旦 less == 0，即达成覆盖条件了，那么就可以考虑移动慢指针，更新合法窗口下的 ansLeft 和 ansRight，试图'破坏'覆盖条件需要让 less != 0，但并不是每次慢指针移动都会破坏覆盖条件，如果移动慢指针之前，慢指针指向的字符cnt[array[left]] == 0，那么说明一旦移动这个慢指针就会让窗口中该字符数量小于 t 中该字符数量，只有在此时 less 才会++，cnt[array[left]] 和 left 的话照常++即可。这样一来就相当于做了两处优化，一处是利用一个数组哈希干了两个数组哈希的事情，另一处就是使用变量 less 直接代替了 isCovered 方法进行判断，两处优化其实是捆绑在一起的。
总结：
相信大家发现了最小覆盖子串和水果成篮两道题目滑动窗口的一个不同点，那就是在水果成篮中，快指针的移动是破坏窗口的合法性，慢指针是维护窗口的合法性。而最小覆盖子串中则是截然相反，由此可以看出在滑动窗口中快慢指针的作用不是固定的，大家需要根据题意仔细辨别。
