算法【滑动窗口】

滑动窗口指的是维持左、右边界都不回退的一段范围，来求解很多子数组（串）的相关问题。

滑动窗口的关键是找到范围和答案指标之间的单调性关系（类似贪心）。

滑动过程：滑动窗口可以用简单变量或者结构来维护信息。

求解大流程：求子数组在每个位置开头或结尾情况下的答案（开头还是结尾在于个人习惯）。

下面通过几个题目加深理解。

题目一

测试链接：https://leetcode.cn/problems/minimum-size-subarray-sum/

分析：如果判断左右边界不回退是应用滑动窗口的关键。设滑动窗口代表以right为结尾的满足条件的最短子数组。假设存在一个满足条件的最短子数组，那么，将left回退，也就是左移也一定会满足条件，而我们是要求最短的子数组，所以确定了right的情况下，left是不会回退的。然后right继续右移，寻找更多情况。直到找到满足条件的子数组，再判断left是否需要右移。遍历数组即可找到最短子数组的长度。代码如下。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ans = 100005;int left = 0, right = 0;int sum = 0;for(;right < nums.size();++right){sum += nums[right];if(sum >= target){while (sum - nums[left] >= target){sum -= nums[left++];}ans = ans < (right - left + 1) ? ans : (right - left + 1);}}return ans == 100005 ? 0 : ans;}
};

其中，将ans初始化为100005是因为nums数组最长为100000，只要比这个数大就行。

题目二

测试链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/

分析：设滑动窗口为以right为结尾的符合条件的最长子串。可以通过一个数组记录每个符号最晚出现的下标。当right来到一个字符的时候，把left置为right最晚出现位置下标加1和left的最大值，这时候ans和right-left+1取最大值，然后更新right处字符最晚出现的下标。遍历数组即可得到最长符合条件的子串长度。代码如下。

class Solution {
public:int lengthOfLongestSubstring(string s) {vector<int> position;int ans = 0;position.assign(256, -1);for(int left = 0, right = 0;right < s.size();++right){left = left > (position[s[right]] + 1) ? left : (position[s[right]] + 1);ans = ans > (right - left + 1) ? ans : (right - left + 1);position[s[right]] = right;}return ans;}
};

其中，position存储各字符最晚出现下标，初始化为-1，方便对一个未出现过的字符更新left值时，将left更新为0。

题目三

测试链接：https://leetcode.cn/problems/minimum-window-substring/

分析：设滑动窗口为以right为结尾的子串。可以通过一个数组记录，每个字符串t中的每种字符的需要被覆盖的个数，同时用一个变量记录总的需要被覆盖个数。当覆盖个数达到要求时，开始调整left。调整后计算ans和right-left+1的最小值。遍历数组即可求得符合条件的最小子串的长度。代码如下。

class Solution {
public:string minWindow(string s, string t) {if(s.size() < t.size()){return "";}vector<int> cnt;int ans = 100005;int l;int count = -t.size();cnt.assign(256, 0);for(int i = 0;i < t.size();++i){--cnt[t[i]];}for(int left = 0, right = 0;right < s.size();++right){if(cnt[s[right]] < 0){count++;}cnt[s[right]]++;if(count >= 0){while (cnt[s[left]] - 1 >= 0){cnt[s[left++]]--;}if((right - left + 1) < ans){ans = (right - left + 1);l = left;}}}return ans == 100005 ? "" : s.substr(l, ans);}
};

其中，ans设为100005的原因之前说过，cnt数组用来记录每种字符需要被覆盖的次数，当大于等于0时代表对此种字符覆盖完毕，count是总的用来记录覆盖完成与否。

题目四

测试链接：https://leetcode.cn/problems/gas-station/

分析：设滑动窗口为以begin为开头的能否走完全程。从begin开始，只要总油量小于0，begin就前移。直到走下去，发现距离等于数组长度，就可以返回begin。如果遍历完数组没有返回begin，则返回-1。代码如下。

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int length = gas.size();for(int begin = 0, end = 0, soil = 0, distance = 0; begin < length;++begin){while (soil >= 0){if(distance == length){return begin;}end = (begin + distance++) % length;soil += (gas[end] - cost[end]);}soil -= (gas[begin] - cost[begin]);distance--;}return -1;}
};

题目五

测试链接：https://leetcode.cn/problems/replace-the-substring-for-balanced-string/

分析：设滑动窗口为以left为开头，最少需要多长的自由变换的区间，可以符合条件。就是说除了自由变换区间中的字符，其他字符不动，只变换自由变换区间中的字符就可以使这个字符串满足条件。确定下left和right之后，更新ans，右移left，而right并不需要回退。这是因为如果left到right区间是自由变换区间，那么left到right+1区间也是自由变换区间。同理，如果left到right-1区间不是自由变换区间，则left+1到right-1区间也不是自由变换区间。所以当left右移时，right并不需要回退。代码如下。

class Solution
{
public:int cnt[4] = {0};bool ok(int num){for (int i = 0; i < 4; ++i){if (cnt[i] > num){return false;}}return true;}int get_index(char ch){switch (ch){case 'Q':return 0;case 'W':return 1;case 'E':return 2;case 'R':return 3;}return -1;}int balancedString(string s){int length = s.size();int num = (length >> 2);for (int i = 0; i < length; ++i){++cnt[get_index(s[i])];}if (cnt[0] == num && cnt[1] == num && cnt[2] == num && cnt[3] == num){return 0;}int ans = length;for (int left = 0, right = 0; left < length; ++left){while (!ok(num) && right < length){--cnt[get_index(s[right++])];}if (ok(num)){ans = ans < (right - left) ? ans : (right - left);}++cnt[get_index(s[left])];}return ans;}
};

其中，cnt数组是用来记录除滑动窗口外每种字符的个数，ok方法判断当前滑动窗口是否可以作为自由变换区间。注意，代码中区间为左闭右开，即[left, right)。

题目六

测试链接：https://leetcode.cn/problems/subarrays-with-k-different-integers/

分析：这个题可以将其分解出来，我们可以写一个f方法用来计算子数组中小于等于k种整数的子数组个数。而要求题目的解只需要f(k)-f(k-1)即可。而分解出来的f方法则可以分析出单调性使用滑动窗口求解。代码如下。

class Solution {
public:vector<int> cnt;int f(int num, vector<int>& nums){cnt.assign(20001, 0);int ans = 0;int count = 0;for(int left = 0, right = 0;right < nums.size();++right){if(cnt[nums[right]]++ == 0){++count;}while (count > num){if(--cnt[nums[left++]] == 0){--count;}}ans += (right - left + 1);}return ans;}int subarraysWithKDistinct(vector<int>& nums, int k) {return f(k, nums) - f(k-1, nums);}
};

其中，count为种类数。

题目七

测试链接：https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/

分析：此题也是一样的，如果直接求解，单调性很难分析出来。我们可以将其分解为子串中只能有i种字符，每种字符必须出现的次数必须大于等于k。只需将i从1到26遍历一次，即可找到符合条件的最大子串长度。代码如下。

class Solution {
public:vector<int> cnt;int longestSubstring(string s, int k) {int ans = 0;int length = s.size();for(int i = 1;i <= 26;++i){cnt.assign(26, 0);for(int left = 0, right = 0, kind = 0, match = 0;right < length;++right){if(cnt[s[right] - 'a'] == 0){++kind;}if(cnt[s[right] - 'a'] == k-1){++match;}++cnt[s[right] - 'a'];while (kind > i){--cnt[s[left] - 'a'];if(cnt[s[left] - 'a'] == k-1){--match;}if(cnt[s[left] - 'a'] == 0){--kind;}++left;}if(match == i){ans = ans > (right - left + 1) ? ans : (right - left + 1);}}}return ans;}
};

其中，kind为[left, right]区间字符种类数，match为区间中大于等于k的字符种类数。