算法练习——滑动窗口
前言：滑动窗口的难点不在于怎么编写代码，而在于如何想到这题是用滑动窗口的算法去解决。其次滑动窗口的左端和右端在滑动时窗口内数据存在单调性。
一：长度最小的子数组
题目要求：
解题思路：
对于第一道滑动窗口算法题而言，去熟悉这一过程，想想这个过程是怎么得到最终答案的，不用考虑为什么这题要使用滑动窗口。
题目要求是：找几个相邻的数据，他们的和大于等于target，要你求出相邻数据长度最小的值。
如果通过暴力算法，能解决，但是肯定会超时。暴力算法的缺陷时，重复的数据会多次计算，
问：那么如何优化算法，才能够避免重复计算呢？
答：我也答不出来，但是可以通过下图来尝试解释优化的过程。
我们的第一目标是要使得连续的几个数据相加的和 ≥ target，
那么我们定义一个 sum，
让 sum += arr[right++]，直至满足条件时（示例1），如下图：
此时已经满足了题给条件。
问：接下来该怎么做呢？
答：定义一个 len 去记录实时的数据范围的长度。
问：定义好了然后呢？让right++吗？
答：显然right此时不应该++，因为再往右++，始终满足范围内数据大于 target ，且 len 不是我们所要的最小值。因此此时应该变动 left 了。
问：left 仅仅只是++吗？
答：显然也不是，如果仅仅是对left++ 的话，sum的数据仍然≥target，所以再left++之前，需要先更新sum的数据，即 sum-=arr[left]，且应该是循环这个过程，直至sum不满足条件，之后right再次++，直至循环结束。
在这一过程，可以看到，当right为2时，我们让left++，这样就少考虑了right 右边 4 3 的情况，在后续遍历中，同样会避免对重复或者是无用数据的计算次数，因此在这一过程中，优化了算法。
实现代码：
int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int len = INT_MAX;int sum = 0;for(int left = 0,right = 0;right < n;){sum+=nums[right];while(sum >= target){len = min(len,right - left + 1);//满足target条件时，更新len 再做变动sum -= nums[left];left++;}right++;}if(len == INT_MAX){return 0;}else{return len;}}二：无重复字符的最长子串
题目要求：
解题思路：
上一题是借助 sum 是否满足target 来判断是否要出窗口
此题需要用到hash表（博主此时还没学过哈希，将哈希的思想理解成计数排序的思想）的思路去判断是否需要出窗口
借助下图来解释思路（示例1）：
定义一个数组 int hash[128] = {0}；先前我们学过计数排序的思想，即对应下标位置处的数据++；
hash[arr[right++]]；right在向右遍历的过程中，对应的下标会不断++
注：arr[right]是字符数据，数组会将字符数据转换成对应的ASCII码值，即对应下标的数据会+1。
当 right 来到该位置处时，此时hash数组中，对应的下标位置处的数据已然为2，此时说明字串已经重复，此时需将a的ASCii码对应下标位置的数据--，再令left++
实现代码：
int lengthOfLongestSubstring(string s) {int hash[128] = {0};int n = s.size();int len = 0;for(int left = 0,right = 0;right <n;){hash[s[right]]++;while(hash[s[right]] > 1){hash[s[left]]--;left++;}len = max(len,right - left+1);right++;}return len;}三：将x减到0的最小操作数
题目要求：
解题思路：
这道题的关键在于逆向思维，读了这么多年书了，逆向思维大家应该都不陌生了。
如果我们直接做这道题，会发现既要在左边遍历，又要在右边遍历，还要对比数据大小，那么这道题的难度就会变得很夸张。
不妨多思考一下，换一个角度考虑。例如不去找两头的数据，而是中间的呢？不难发现，中间的数据是连在一起的，中间数据的值 = 数据总和 - x
那么这道题就被转换成了：在数组中找一串连续的数据，满足以下两个要求
①：连续数据的和为：数据总和 - x
②：连续数据的长度最长
滑动窗口算法：
该算法有固定的部分：将数据入窗口，将数据出窗口
变化的部分是：出窗口的条件，以及何时更新我们想要的结果，和部分细节上的问题。
以下图为例：目标找满足和为20的数
定义 sum = 0；
开始时，持续入窗口 sum+= nums[right]; right++;
当指针来到下图位置时，sum > 20
此时需要出窗口，并更新窗口内数据大小，直至他不满足 > 20
当left指针来到下图位置时，恰巧找了我们需要的目标值
此时更新结果值，并继续循环直至结束。
代码实现：
int minOperations(vector<int>& nums, int x) {int sum_num = 0;for(int i = 0; i < nums.size(); i++){sum_num += nums[i];}int target = sum_num - x;if(target < 0){return -1;}int sum = 0;int len = -1;for(int left = 0, right = 0; right < nums.size();right++){sum += nums[right];while(sum > target){sum -= nums[left];left++;}if(sum == target){len = max(len , right - left + 1);}}if(len == -1){return len;}else{return nums.size() - len;}}注：上述代码有个注意点：target 可能为负，此时需要直接返回 -1
四：水果成篮
题目要求：
解题思路：
分析：简化一下题目，在一个整型数组fruit中，找到只包含两种数字的最大子串。
思路：借助哈希表——unordered_map<int,int> hash;来记录每种数字，以及其出现的次数
以示例4为例，初始情况如下图
进窗口：
hash[f[right]]++; 记录当前水果，以及其出现次数，当right如下图位置时，需要出窗口
出窗口：
当 hash.size() > 2 时，说明此时窗口内数字种类已超过2，不满足题目要求。。此时left需要++，但是left++前，需更新当前窗口信息，hash[f[left]]--;
当hash[f[left] == 0];时，此时需将该数字从hash表中删除
需要循环出窗口，直至满足数字个数要求，如下图所示：
更新结果：
每次进窗口时，更新Max值
实现代码：
class Solution {
public:int totalFruit(vector<int>& f) {unordered_map<int,int> hash;int Max = 0;for(int left = 0,right = 0; right < f.size(); right++) {hash[f[right]]++;while(hash.size() > 2) {hash[f[left]]--;if(hash[f[left]] == 0) {hash.erase(f[left]);}left++;}Max = max(Max,right-left+1);}return Max;}
};五：找到字符串中所有字母异位词
题目要求：
解题思路：
法一（以示例1为例）：如下图定义两个变量
定义一个哈希表——int hash[26] = {0}; 来记录每个字母出现的个数
进窗口：
hash[s[right] - 'a']++;直至如图所示
出窗口：
当right - left + 1 > 子串长度(p.size())时，left需++，在left++前，需要先更新当前窗口，即hash[s[left] - 'a']--;
注：本题中，窗口大小是固定的，因此只需要出一次窗口即可
更新结果：
当 right - left + 1 = 子串长度，写一个判断函数，将hash与p传入，判断是否为异位词，是则更新结果
法二（以示例1为例）：区别于法一的是，通过维护另一个count变量，来更新结果。
初始变量如下图所示：
解释：
hash1[26]用于记录子串p中，所有字母出现的个数
hash2[26]用于记录字符串s中，left~right所有字母出现的个数
进窗口：
hash2[s[right] - 'a']++;
判断 if(hash2[s[right] - 'a'] <= hash1[s[right] - 'a']) 若满足条件，说明此时hash2中进入了一个有效的字母，所以count++
解释：当前right处的字母为c，hash2[s[right] - 'a']++;将字母c插入到了hash2中，因为hash1中也包含了字母c，且只有一个，那么说明hash2中插入的字母为有效字母，count需要++，👉：假设插入的第二个字母也是c，但hash1中只有一个字母c，那么此时hash2中字母c的个数大于hash1中字母c的个数，说明第二次插入的c不是有效字母，因此count不++；
👉：假设插入的第二个字母是e，但是hash1中没有字母e，说明插入的也不是有效字母，因此count不++
循环进窗口直至如图所示：
出窗口：
当right - left + 1 > 子串长度时，需要出窗口，如图所示
hash2[s[left] - 'a']--;
判断if(hash2[s[left] - 'a'] < hash1[s[left] - 'a']) count--;
解释：
需要判断当前出hash2的字母是否为有效字母，若为有效字母，则count--;如图所示
可以看到此时count == 2，无法满足更新结果的条件
更新结果：
当 count == 子串长度时，说明此时hash2和hash1互为异位词。left为答案之一。如图所示
实现代码：
法二：
class Solution { public:vector<int> findAnagrams(string s, string p) {int hash1[26] = {0}, hash2[26] = {0};for(auto& w : p) {hash1[w - 'a']++;}vector<int> ret;for(int left = 0, right = 0, count = 0, len = p.size(); right < s.size(); right++) {hash2[s[right] - 'a']++;if(hash2[s[right] - 'a'] <= hash1[s[right] - 'a']) {count++;}if(right - left + 1 > len) {hash2[s[left] - 'a']--;if(hash2[s[left] - 'a'] < hash1[s[left] - 'a']) {count--;}left++;}if(right - left + 1 == len && count == len) {ret.push_back(left); }}return ret;} };六：串联所有单词的子串
题目要求：
解题思路：
明确变量：
int len = words[0].size(); → words中，每一个子串的长度
int total = words.size(); → words的个数：
以示例1为例：
思考一个问题：left和right该怎么更新？每次+1吗？
答：显然不可以，如果一个一个更新，那么每次只能统计一个字母，当满足right - left + 1 = len 时，在记录当前字符串，这显然太复杂了！！！！所以left和right每次应该+=len
定义一个变量 string in = s.substr(right,len);来构建当前s中的子串，进而做进一步的讨论。
思考另一个问题：这么做带来的问题就是，以第二个或者第三个为起始的子串没法遍历。
答：为此我们需要在外部再套一层循环，循环len次。如图所示，一次讨论一种情况
思路：明确上述后，本题的思路就和第五题的法二没有太大区别了。
明确变量：
unordered_map<string,int> hash1; 用于记录p中所有字符串出现的个数
unordered_map<string,int> hash2; 用于记录当前left~right+len所构成的字符串出现的次数
起始如图所示：
进窗口：
string in = s.substr(right,len);
hash2[in]++;
判断 if(hash1.count(in) && hash2[in] <= hash1[in]) count++；若当前进窗口的字符为有效字符，则count++；
出窗口：
当right - left + 1 > total * len 时，需要出窗口，因为窗口大小固定，所以只需要出一次。
string out = s.substr(left,len);
hash2[out]--;
判断 if(hash1.count(out) && hash2[out] < hash1[out]) 若当前出窗口的字符为有效字符，则count--；
left += len;
可以看到此时窗口大小满足题目答案要求，但是count = 1，说明有效字符串个数不足，因此此时left处不满足题目要求。
更新结果：
如果count == total，则left位置处为答案之一。
实现代码：
class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string,int> hash1;for(auto str : words) {hash1[str]++;}vector<int> ret;int len = words[0].size(), total = words.size();for(int i = 0; i < len; i++) {unordered_map<string,int> hash2;for(int left = i, right = i,count = 0; right + len <= s.size(); right += len) {string in = s.substr(right,len);hash2[in]++;if(hash1.count(in) && hash2[in] <= hash1[in]) {count++;}if(right - left + 1 > total * len) {string out = s.substr(left,len);hash2[out]--;if(hash1.count(out) && hash2[out] < hash1[out]) {count--;}left += len;}if(count == total) {ret.push_back(left);}}}return ret;}
};七：最小覆盖子串
题目要求：
解题思路：
思路：
明确变量：
int Begin = -1; 用于记录最小子串的起始位置
int Min = INT_MAX; 用于记录最小子串的长度
int hash1[128] = {0}; 用于记录子串t中所有字母出现的个数
int hash2[128] = {0}; 用于记录字符串s中 left~right 所有字母出现的个数
int count = 0; 用于记录hash2中，有效字母的个数
初始如下图所示：
进窗口：
hash2[s[right]]++;
判断if(hash2[s[right]] <= hash1[s[right]])，若满足条件，说明此时进入hash2的为一个有效字母，则count++；
出窗口：
当count == t.size()时，说明此时hash2中已经包含了hash1中所有的字母，如图所示：
1.在窗口中更新结果
判断if(right - left + 1 < Min)，若满足条件，则Begin = left，Min = right - left + 1；
2.再出窗口
hash2[s[left]]--；
3.更新窗口信息
if(hash2[s[left]] < hash1[s[left]]) 若条件成立，则说明出窗口的字母为有效字母，则count--；
4.left++；
注：此处需要循环出窗口
解释：第一次满足条件时，因为hash2中出去的第一个字母就是有效字母，为此循环直接结束，当第二次满足条件时，此时如图所示：
hash2中出去的第一个字母不是有效字母，count仍然等于3，
若并非循环出窗口，那么在right到字符串末尾时，都无法得到我们想要的答案，
若为循环出窗口，可以看到，hash2中会将无效字母循环去除，在这个过程中Min的值会逐渐减小，直至有效字母的个数变为2，此时得到一个临时的Min和Begin。
当第三次满足条件时，如图所示：
循环出窗口至如图所示：
因为是先更新的Min和Begin，left在++，所以此时Min和Begin就是我们想要的答案。
实现代码：
class Solution {
public:string minWindow(string s, string t) {int hash1[128] = {0};int hash2[128] = {0};for(auto& w : t) {hash1[w]++;}int Min = INT_MAX;int Begin = -1;for(int right = 0, left = 0, count = 0; right < s.size(); right++) {hash2[s[right]]++;if(hash2[s[right]] <= hash1[s[right]]) {count++;}while(count == t.size()) {if(right - left + 1 < Min) {Min = right - left + 1;Begin = left;}hash2[s[left]]--;if(hash2[s[left]] < hash1[s[left]]) {count--;}left++;}}if(Begin == -1) {return "";}else {return s.substr(Begin,Min); }}
};