滑动窗口算法
文章目录
- 滑动窗口算法
-
- 双指针模板
- 滑动窗口
- 在原串中寻找目标子串
-
- 无重复字符的最长子串
-
- （哈希表+双指针->滑动窗口）
- （优化滑动窗口）
- *最小覆盖子串
-
- （滑动窗口）
- 长度最小的子数组
-
- （暴力循环累加）TLE
- （前缀和+二分）
- （滑动窗口）
- 找到字符串中所有字母异位词
-
- （滑动窗口）
- 字符串的排列
-
- （滑动窗口）
- 在替换过后的字符串中寻找目标子串
-
- *替换后的最长重复字符
-
- （滑动窗口）
- 最大连续1的个数 lll
-
- （暴力）
- （二分+前缀和）
- （滑动窗口）
- 尽可能使字符串相等
-
- （前缀和+二分）
- （滑动窗口）
- 删除一个元素以后全为1的最长子数组
-
- （二分+前缀和）
- （滑动窗口）
双指针模板
模板一：
左指针移动，操控右指针一步到位（到达符合条件的最后一个字符）。这个模板一般用于提取一段连续的字符。
void findSubStr(string& str) {
for (int left = 0; left < str.size(); left ++) {
int right = left;
while (right < str.size() && ...(条件)) right ++;
// 要求
left = right - 1;
}
}
模板二：
右指针移动，操控左指针向右伸展，主要处理左边界不符合条件的字符。这个模板比较万能可以处理连续的子串或者子数组问题。
void findSubStr(string& str) {
int left = 0, right = 0;
while (right < str.size()) {
char c = str[right];
right ++;
// 延伸右指针，处理字符c
while (/*[left, right)不满足搜索子串的要求*/) {// 有时这里可以写成if
char d = str[left];
left ++;
// 收缩左指针，处理不符合条件字符d
}
}
}
滑动窗口
滑动思想核心：利用双指针维护一个可以变动大小的可移动窗口，而扩展和收缩窗口的标准是：利用需要搜索的字符需要满足的要求来判断窗口的边界情况。
在原串中寻找目标子串
无重复字符的最长子串
（哈希表+双指针->滑动窗口）
使用暴力循环搜索所有子串的方法的缺点在于：如果两个子串的前缀是一样的时候，那么两个字符串是有关联的，也就是如果前一个字符串中已经有重复的字符了，那么和该字符串有相同的前缀子串的所有字符串都是有重复字符的字符串。
知道了暴力方法的缺点就可以对症下药，使用两个指针
left
和
right
。**核心思想：
right
主动的往右移动，
left
被动的往右移动。**意思就是：
right
指针一直往右遍历字符串中的每一个字符，同时为了记录两个指针形成的一个“窗口”中的字符是否有重复，所以可以将字符串放入哈希表中（哈希表的查询时间需要O(1)）,这里因为字符所需的空间是一定的，所以使用数组作为哈希表。
right
指针在将字符放入窗口的同时检查是否有重复元素，如果有重复的元素就“收紧”
left
指针，直到重复的字符不在窗口中，而在整个过程中窗口的最大大小就是无重复的最长子串。
滑动窗口的核心就是维护了一一段没有重复字符的连续子串，
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> window;
int left = 0, right = 0;
int len = 0;
while (right < s.size()) {
char c = s[right ++];
window[c] ++;
while (window[c] > 1) {// 出现重复的字符就收缩窗口的左边界
char d = s[left ++];
window[d] --;
}
len = max(len, right - left);
}
return len;
}
};
（优化滑动窗口）
上面的方法是如果发现
right
指针“收纳”了重复的字符就“收紧”
left
指针，但是
left
是一步一步收紧的，也就是窗口中的字符是一个一个弹出窗口的。这是因为窗口中存放的是字符的出现的次数。
如果使用一个窗口存放的是一个字符最后出现的位置下标，等到再遇到相同字符的时候，就可以直接获得上一次那个重复的字符的位置，这样就可以直接达到该位置，而不是一步一步的弹出中间的元素。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
if (n <= 1) return n;
vector<int> windows(128, -1);
int ans = 0, l = 0;
for (int r = 0; r < n; r ++) {
if (windows[s[r]] != -1) {
l = max(l, windows[s[r]] + 1);
}
windows[s[r]] = r;
ans = max(ans, r - l + 1);
}
return ans;
}
};
*最小覆盖子串
（滑动窗口）
这里的循环不变量是
[left, right)
，维护一个滑动窗口
[left, right)
，窗口一直往右扩展直到窗口中全部覆盖了目标字符串
t
。然后就可以计算并更新窗口的大小（也就是覆盖的子串的长度），同时因为要保证是最小的覆盖子串，所以在更新的同时就要使得窗口的左边界往右紧缩直到字符串不能覆盖目标串，就继续的使得右边界向右拓展。
思路并不难，难的是实现的细节，代码的最后有注释。
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> window, need;
for (char ch : t) need[ch] ++;
int left = 0, right = 0;
int start = 0, len = INT_MAX;
int vaild = 0;
while (right < s.size()) {
char c = s[right];
right ++;
if (need.count(c)) {
window[c] ++;//*
if (window[c] == need[c]){//*
vaild ++;
}
}
// 缩小窗口
while (vaild == need.size()) {
// 更新答案
if (right - left < len) {
len = right - left;
start = left;
}
char d = s[left];
left ++;
if (need.count(d)) {
if (window[d] == need[d]) {//*
vaild --;
}
window[d] --;//*
}
}
}
return len == INT_MAX ? "" : s.substr(start, len);
}
};
有几个易错点需要说明一下：
1、如何判断是否滑动窗口内已经包含了目标字符串？
使用两个哈希表，
need
来标记目标字符串中的所需的字符和字符个数，
window
来记录滑动窗口内已经包含的额字符和字符个数，另外使用一个变量
vaild
标记互动窗口中已经覆盖的字符串的有效长度。当
vaild==t.size()
就说明滑动窗口中已经覆盖了目标字符串。（
window
哈希表是用来防止覆盖字符串的有效长度重复记录，因为是有当
window[c] < need[c]
的时候才可以
vaild++
。如果已经超出目标字符串中的字符个数的时候，就不用增加有效长度了。）
2.在上面*注释的地方一定要注意，判断语句只是操作
vaild
，而对
window
的操作在判断之外。为什么要强调这一点？因为会有同学觉得为什么要让哈希表记录重复的字符的个数。只记录目标字符串中的字符最多的个数不行吗？
注意：这里的vaild不是字符串中的字符的个数，而是字符的种类数，比如说t字符串中有2个a，只有当窗口内的a字符的个数到达2的时候，vaild才可以加一。
解释是：如果将对
window
的操作放在
if (window[c] == need[c])
判断中，那么不能得到最小的覆盖子串，因为只是将字符的个数仅限于目标字符串中，如果目标字符串只有一个
a
，但是滑动窗口中有
aa
，那么当窗口左边界向右收的时候，只收了一个
a
，但是这并不是最小的覆盖，因为后面还有一个
a
，只有把后面的
a
也收了才是不满足目标字符串的底线，而还有一个字符串就说明滑动窗口还有收缩的余地，所以为了使得覆盖子串的长度最小，必须要让滑动窗口记录所有的字符才可以。
3.记录的字符串的长度的时机，在哪里？
因为在
while
循环中意思是窗口内已经可以覆盖最小子串了，但是为了找到最小的子串，所以右窗口向右延伸，左窗口向右收缩，这个意思满足了寻找到目标串的要求，所以在
while
左指针向右延伸的时候更新答案。
只使用一个哈希表的方法
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> need;
for (char ch : t) need[ch] ++;
int left = 0, right = 0;
int start = 0, len = INT_MAX;
int vaild = 0;
while (right < s.size()) {
char c = s[right];
right ++;
if (need.count(c)) {
if (need[c] > 0) // >0说明窗口内没有全部覆盖字符串
vaild ++;
need[c] --;
}
while (vaild == t.size()) {// 缩小窗口
if (right - left < len) {// 更新答案
len = right - left;
start = left;
}
char d = s[left];
left ++;
if (need.count(d)) {
if (need[d] == 0)
vaild --;
need[d] ++;
}
}
}
return len == INT_MAX ? "" : s.substr(start, len);
}
};
长度最小的子数组
（暴力循环累加）TLE
暴力累加就是枚举每一个数，然后一直扩展连续子数组直到数组和
>target
，继续下一个子数组。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int len = INT_MAX;
for (int i = 0; i < nums.size(); i ++) {
int sum = 0;
for (int j = i; j < nums.size();j ++) {
sum += nums[j];
if (sum >= target) {
len = min(len, j - i + 1);
}
}
}
return len == INT_MAX ? 0 : len;
}
};
- 时间复杂度O(N2)
（前缀和+二分）
想要知道一段区间的和，然后和
target
比较就可以使用前缀和的方法做到O(1)查询数组和。然后二分出所有的区间和。找到子数组最小的一个。（我这里二分区间和的办法就从第
i
个数开始加上
target
，这样区间和就是从
i
位置开始的。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// 前缀和
vector<int> sum(nums.size() + 1, 0);
for (int i = 1; i <= nums.size(); i ++) {
sum[i] = nums[i - 1] + sum[i - 1];
}
// 二分
int len = INT_MAX;
for (int left = 0; left < nums.size(); left ++) {
int right =
lower_bound(sum.begin(), sum.end(), sum[left] + target) -sum.begin();
// 这里的right在前缀和数组中是right闭区间,在原数组中是right-1闭区间
// 如果数组总和不足target的话,right=nums.size()+1
if (right > nums.size()) break;
len = min(len, right - left);
}
return len == INT_MAX ? 0 : len;
}
};
- 时间复杂度O(NlogN)
（滑动窗口）
滑动窗口核心思想：主动扩展右边界，到一定程度的时候（题目具体要求）就收缩左边界。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int len = INT_MAX;
int left = 0, right = 0;
int sum = 0;
while (right < nums.size()) {
// 扩展窗口
sum += nums[right];
right ++;
// 收缩窗口
while (sum >= target) {
len = min(len, right - left);
sum -= nums[left];
left ++;
}
}
return len == INT_MAX ? 0 : len;
}
};
- 时间复杂度O(N)
找到字符串中所有字母异位词
（滑动窗口）
这道题目题目和覆盖最小子串拿到题目很像，唯一的不同点在于覆盖最小子串中寻找的子串力可以有不是目标字符串中的字符。但是本题必须要找到字符串的异形词，也就是不能有其他的字符出现。
既然还是寻找子串，所以还是可以使用两个哈希表来记录对应字符的个数，还是使用
if(need.count(c))
来判断记录字符到寻找的子串中。
但是有一个难点在于如何收缩窗口，如果是
vaild == need.size()
的时候，那万一字符串中有其他字符就可以了。而且如果发现一个不满足要求的字符出现在目标字符串中间，是立刻收缩窗口，还是先不管继续往后延伸？
有一个很暴力的方法就是：判断字符串的长度
if(right - left == need.size())
（这里字符串的覆盖范围是
[left, right)
，所以
right - left
就是字符串的长度）就收缩窗口。换言之，如果字符串已经到达了目标字符串的长度就是目标字符串的一个上限，这时候判断的话就可以同时的解决上面的问题。如果该子串就是目标子串的话，就可以记录下左边界的索引；如果该子串中包含其他的字符就收缩左边界并判断一下是否去掉的字符在目标子串中。
**注意这里使用的
if
因为左边界一定收缩，所以只能判断一次，有的同学会觉得有一点奇怪，不应该试是将所有的不符合字符都去除掉吗？不应该使用
while
直接全部去掉吗？**这话确实没错，但是窗口收缩边界的判断条件就是以字符串的长度为依据的，所以只能使用if判断，但是这并不影响结果，这是因为每一次都会去掉一个字符，如果去掉这个字符后子串中还是有其他的字符，那么在后面判断的时候总有一次可以将它删除掉，这样并影响窗口的左边界的判断。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
unordered_map<char, int> window, need;
for (auto ch : p) need[ch] ++;
int left = 0, right = 0;
int vaild = 0;
vector<int> ans;
while (right < s.size()) {
char c = s[right];
right ++;
if (need.count(c)) {
window[c] ++;
if (window[c] == need[c])
vaild ++;
}
// 这里因为每次都只添加一个字符,所以可以直接使用if判断一次即可，而不用while
if (right - left == p.size()) {
if (vaild == need.size())
ans.push_back(left);
char d = s[left];
left ++;
if (need.count(d)) {
if (window[d] == need[d])
vaild --;
window[d] --;
}
}
}
return ans;
}
};
字符串的排列
（滑动窗口）
同找到字符串中所有字母的异位词
class Solution {
public:
bool checkInclusion(string s1, string s2) {
unordered_map<char, int> window, need;
for (auto c : s1) need[c] ++;
int left = 0, right = 0;
int vail = 0;
while (right < s2.size()) {
char c = s2[right];
right ++;
if (need.count(c)) {
window[c] ++;
if (window[c] == need[c])
vail ++;
}
while (right - left == s1.size()) {
if (vail == need.size()) return true;
char d = s2[left];
left ++;
if (need.count(d)) {
if (window[d] == need[d])
vail --;
window[d] --;
}
}
}
return false;
}
};
在替换过后的字符串中寻找目标子串
*替换后的最长重复字符
（滑动窗口）
首先可以想一下暴力做法：枚举出所有的子串，然后计算出子串中需要替换的字符的个数，发现
1.如果一个字符串替换了k个字符后可以做到都是重复的字符，那么最长的重复字符串一定不会比这个字符串的长度要小。
2.如果发现一个字符串替换了k个字符后，依然不能成为全是重复的字符串的话，这是字符串就算扩展了右边界也不能使得字符串成为全部是重复字符的字符串，所以这时就没有必要搜索和这个字符串有相同字符串前缀的字符串，也就是可以使用滑动窗口使得左边界向右紧缩。
经过上面的分析，发现使用滑动窗口的方式可以避免重复的考虑很多情况。
知道了使用滑动窗口之后，必须要判断什么情况下窗口内的重复字符最多，而且怎么表示那k个被替换的字符？
这里可以使用一个小技巧，在替换字符的时候并不真正替换字符串中的字符，而是统计重复字符的最大值
maxCount
，然后比较窗口内的字符串长度，当滑动窗口内的字符串长度
< maxCount+k
的时候，说明替换字符已经达到了上限k次，不能再替换了，这是就应该收缩滑动窗口。
还有几个问题在看完代码之后来解释：
class Solution {
public:
int characterReplacement(string s, int k) {
unordered_map<char, int> window;
int left = 0, right = 0;
int len = 0, maxCount = 0;
while (right < s.size()) {
char c = s[right ++];
window[c] ++;
maxCount = max(maxCount, window[c]);// 记录当前最长的重复字符的个数
if (right - left > maxCount + k) {// 这里使用while也是可以的
char d = s[left ++];
window[d] --;
}
// 更新滑动窗口的大小
// 这一行代码也可以省略，因为滑动窗口会一直维持最大的状态不会倒退
len = max(len, right - left);
}
return len;
}
};
1.什么时候滑动窗口的左边界向右收缩？
注意这里不是
right - left == maxCount + k
，也就是说不是滑动窗口内的字符被替换了k个字符后就立刻要收缩滑动窗口的，而是被替换了k个字符之后，如果接在后面的字符还是重复最多的字符也就是让
maxCount++
的字符的话，还是可以继续扩展滑动窗口的。只有当字符是一个新的字符的时候（不是重复次数最多的字符），才可以收缩窗口。
2.maxCount在收缩窗口后，重复最多的字符可以会改变或者会减少，但是为什么收缩窗口后并不维护窗口的大小呢？
这是因为没有必要，如果要维护maxCount的话需要遍历一遍窗口内的字符，但是由于要求出的字符串一定是最长的重复字符串，而且在扩展窗口的时候也会更新
maxCount = max(maxCount, window[c])
，所以
maxCount
应该只会增加不会减少。
3.更新答案的位置应该在哪里？
在前面几道滑动窗口的题目中，答案的更新都在收缩窗口的时候。因为在窗口收缩的时候正好到了目标子串的要求，而这里的
if
收缩窗口的时候，正好是字符串不满足条件的时候，所以一定要在
if
条件判断后也就是在窗口收缩后，字符串中的重复个数最大的时候再更新答案。
最大连续1的个数 lll
（暴力）
搜索出字符串所有的子串，然后计算出子串中0的个数（也就是需要替换数字的个数）判断是否满足最大的可替换范围，最后得出所有满足要求的子数组的长度。
（二分+前缀和）
要想快速地计算出子数组中0的个数就可以使用前缀和的技巧，因为数组中只要0或者1，所以可以将0记作1,1记作0，这样就可以使用
sum[right] - sum[left - 1]
，快速的计算出
[right, left]
区间中的0的个数了。
但是要注意的是：前缀和中的
right
和
left
都是在原数组中的下标中+1的，所以在前缀和数组和原数组中会有向右一位的偏差，所以看起来很变扭。
sum[right] - sum[left-1]
可以计算出
[left, right]
之间的0的个数，但是本题如果将所有的子数组都列出来就太麻烦了，所以可以想到如果
sum[right] - k
就是区间中有k个0的左边界。这样只要遍历枚举区间的右端点就可以立刻定位出区间的左端点。
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
vector<int> sum(nums.size() + 1, 0);
for (int i = 1; i <= nums.size(); i ++) {
sum[i] = sum[i - 1] + (1 - nums[i - 1]);
}
int ans = 0;
for (int right = 1; right <= nums.size(); right ++) {
int left =
lower_bound(sum.begin(), sum.end(), sum[right] - k) - sum.begin();
// 因为i是前缀和数组中的下标，所以i是对应原数组下标的下一个位置，因而区间是[left,right)
// 根据这点可以知道数组的长度是right-left
ans = max(ans, right - left);
}
return ans;
}
};
（滑动窗口）
也可以使用滑动窗口来避免重复的搜索和计算拥有相同前缀的子数组。
收缩窗口的条件：窗口中1的个数+替换的个数已经小于了窗口中的数字的个数，也就是说窗口中的0的个数已经多出了替换的次数。
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
vector<int> window(3, 0);
int left = 0, right = 0;
int maxCount = 0;
int len = 0;
while (right < nums.size()) {
int r = nums[right++];
window[r] ++;
// 当子数组中的1的数量+可替换的数量<子数组中的数的个数的时候
// 就是寻找窗口大小的极限，就需要left++,收缩窗口
if (right - left > window[1] + k) {
int l = nums[left ++];
window[l] --;
}
len = max(len, right - left);
}
return len;
}
};
尽可能使字符串相等
（前缀和+二分）
class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
vector<int> sum(s.size() + 1, 0);
// 字符差的前缀和
for (int i = 1; i <= s.size(); i ++) {
sum[i] = sum[i - 1] + abs(s[i - 1] - t[i - 1]);
}
int len = 0;
// 这里的right在前缀和数组和原数组中的含义不同
// 前缀和数组是[left, right],原数组中是[left, right)
// left没有变化是因为前缀和数组前后多了一个sum[0]
for (int right = 1; right <= s.size(); right ++) {
int left =
lower_bound(sum.begin(), sum.end(), sum[right] - maxCost) - sum.begin();
len = max(len, right - left);
}
return len;
}
};
（滑动窗口）
题目的转换：在
maxCost
的消耗内替换字符串s中的字符之后，在替换过后的字符串中找到最长的子串和字符串t对应的字符串相等。
收缩窗口的条件：总消耗
sum
已经大于了最大消耗
maxCost
。此时窗口内的字符消耗已经过大，所以要收缩窗口的左边界。
class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
unordered_map<char, int> window;// 记录字符转换对应的开销
int left = 0, right = 0;
int len = 0;
int sum = 0;// 字符串转换总的开销量
while (right < s.size()) {// 扩展右边界
sum += abs(s[right] - t[right]);
right ++;
while (sum > maxCost) {// 收缩左边界
sum -= abs(s[left] - t[left]);
left ++;
}
len = max(len, right - left);
}
return len;
}
};
删除一个元素以后全为1的最长子数组
本题同最大连续1的个数lll的解法，只是将其中0替换成1的个数换成了1次，并且这里的数字不是替换而是删除，所以最后要在最长数组的基础上-1。
（二分+前缀和）
class Solution {
public:
int longestSubarray(vector<int>& nums) {
vector<int> sum(nums.size() + 1, 0);
for (int i = 1; i <= nums.size(); i ++) {
sum[i] = sum[i - 1] + (1 - nums[i - 1]);
}
int len = 0;
for (int right = 1; right <= nums.size(); right ++) {
int left =
lower_bound(sum.begin(), sum.end(), sum[right] - 1) - sum.begin();
len = max(len, right - left);
}
return len - 1;
}
};
（滑动窗口）
窗口的收缩条件：窗口中1的个数+1次删除机会小于窗口中的数字的个数。
class Solution {
public:
int longestSubarray(vector<int>& nums) {
vector<int> window(3, 0);
int left = 0, right = 0;
int len = 0;
while (right < nums.size()) {
int r = nums[right ++];
window[r] ++;
if (right - left > window[1] + 1) {
int l = nums[left ++];
window[l] --;
}
len = max(len, right - left);
}
return len - 1;
}
};