二刷刷到滑动窗口，发现有一些细节和遗漏，在此补充
实际上关于滑动窗口的题还有一题：最小长度的子数组
进入正题
水果成篮
LeetCode904水果成篮
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
示例 1：
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。
示例 2：
输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
示例 3：
输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
思路
题目的要求，换个说法就是：找到一段数组中的元素，该段元素中类型最多为2种，如果段中元素达到3种就直接停止。我们的目标是使这个段中元素的个数尽可能多
例如：（示例3）
[[1,2],3,2,2]
[[1,2,3],2,2]
如果是从1开始取的话，到3就会停止，最终只能取到[1, 2]，显然这不是题设规则下的最优解
如果我们从2开始取呢？
[1,[2,3],2,2]
[1,[2,3,2],2]
[1,[2,3,2,2]]
最后结果是[2,3,2,2]，这是最优解
这里的“段”，实际上很类似窗口，由此可以联想到滑动窗口算法
我们需要维护的窗口内只能存在两种类型的数，一旦出现第三种，缩小窗口的左边界，直到再次满足条件后，继续使右边界扩大
思路很明确了，那怎么实现呢？关键点是如何记录元素出现次数
根据之前的经验，要记录某种东西出现的次数，可以考虑用哈希表
这里创建一个哈希表unordered_map，键是当前的遍历值，值是出现次数
判断哈希表的大小，一旦大于2，就触发循环，在map中找到以左指针指向的数组值为哈希表键的元素，将其移除即可（注意，要先删除干净其键对应的值，这里在下面细说），同时，left的指针向右移动。
最后，左右指针作差，更新结果保存变量（取最大的保存）
代码
坑（关于map的使用）
思路定下来了，写代码吧
这是根据思路写的第一版
class Solution {
public:
int totalFruit(vector<int>& fruits) {
//定义左指针
int left = 0;
int res = 0;
unordered_map<int, int> typeCount;//定义一个哈希表，键是遍历值
for(int right = 0; right < fruits.size(); ++right){
typeCount[fruits[right]]++;
while(typeCount.size() > 2){//如果类型大于2，开始移动左指针缩小窗口
auto it = typeCount.find(fruits[left]);
if(it != typeCount.end()){//找到左指针对应的键值，删除
typeCount.erase(it);
}
left++;
}
res = max(res, right - left + 1);
}
return res;
}
};
看起来没有什么问题，其实问题挺大的，并且很隐蔽
问题主要出现在以下部分：
auto it = typeCount.find(fruits[left]);
if(it != typeCount.end()){//找到左指针对应的键值，删除
typeCount.erase(it);
}
这里的本意是：在map中找到以fruits[left]为键的元素，然后将其移除。
这是符合我们之前的逻辑推导的，但是在代码落实的时候出问题了
在map中查找某个键对应的值，返回的是一个迭代体，我们可以通过it != typeCount.end()判断是否查找到对应的键值
这里在找到键值对后，我直接把返回的迭代体删了
只删迭代体对象没用啊，map中对应的键值对是不受影响的，也就是说，删了个寂寞
正确删除map中键值对的操作是：
- 使用find找到键值对
- 将键对应的值（it->second）全部删除
- 判断当前键对应的值为0后，删除指向键值对的迭代体
完整代码
根据上述讨论修改后的代码如下：
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int left = 0;//定义左指针
int res = 0;
unordered_map<int, int> typeCount;//定义一个哈希表，键是遍历值
for(int right = 0; right < fruits.size(); ++right){
typeCount[fruits[right]]++;//记录出现次数
while(typeCount.size() > 2){//如果类型大于2，开始移动左指针缩小窗口
auto it = typeCount.find(fruits[left]);//使用find找到键值对，并返回迭代体对象
it->second--;//将键对应的值全部删除
if(it->second == 0){
typeCount.erase(it); //删除指向键值对的迭代体
}
left++;//左指针右移
}
res = max(res, right - left + 1);//将最大值更新到结果变量
}
return res;
}
};
本题思路其实不难想，主要问题出现在代码实现，对于map的使用不熟练
最小覆盖子串
LeetCode76最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
思路
大体思路
从题目给的模板（minWindow）可以得到提示，这题可以用滑动窗口算法解（其实不看也应该能想到）
我们需要维护一个窗口
窗口的右边界不断遍历输入字符串s，往窗口内添加字符，直到当前窗口内出现目标字符串t中的所有字符，此时移动左边界来缩小窗口，取出冗余字符
好了，此题关于滑动窗口部分的思路讨论完毕
很清晰是吧？然后写代码的时候会发现根本写不出
因为很多思路中理所当然的地方用代码很难实现
代码实现思路
那么用代码写的时候应该怎么考虑呢？
我们要维护两个哈希表（unordered_map），hs和ht
ht用与统计目标字符串t中各字符出现的次数；
hs用于记录当前遍历字符出现的次数；（至于为什么是“次数”，后面会说）
定义结果字符串res、左指针变量left.、计数变量count
右指针遍历输入字符串s，将遍历字符加入hs
如果当前遍历字符是目标字符串t中的目标字符，且出现次数小于等于ht中的出现次数，计数变量加1
什么意思呢？
TBD，有空再补，先看代码和注释吧
代码
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int>hs, ht;//用于统计t和s的hash表，键为对应字符，值为出现次数
for(int i = 0; i < t.size(); ++i){//统计t的字符出现次数
ht[t[i]]++;
}
string res;//定义结果字符串
int left = 0;
int count = 0;//用于统计s中目标字符（t中字符）出现的次数
for(int right = 0; right < s.size(); ++right){//遍历字符串s，对应字符出现后在hs记录
hs[s[right]]++;
if(hs[s[right]] <= ht[s[right]]){//如果当前添加的hs值在ht中出现，且次数小于等于ht中的次数，该字符有效，计数加1
count++;
}
//不满足上述条件就说明当前目标字符在hs中出现次数大于ht中次数
while(hs[s[left]] > ht[s[left]]){//此时，要移动左边界去除当前窗口中的冗余字符
//注意，是先减值，再移动left！！！
hs[s[left]]--;//对应减少hs中的值，直到hs中的目标字符出现次数均与ht中相等
left++;//移动左边界
}
//更新res
if(count == t.size()){//当count计数与t长度相等时表示当前窗口中已经包含有全部t中的目标字符，需要更新res
if(res.empty() || res.size() > right - left + 1){//结果字符串为空或其长度大于当前窗口长度
res = s.substr(left, right - left + 1);//截取当前窗口内字符串作为结果字符串
}
}
}
return res;
}
};