算法沉淀二：滑动窗口
目录
一、滑动窗口
1.什么是滑动窗口
顾名思义，滑动窗口，就是一个可变大变小的区间，左边为left， 右边为right，left 和 right 构成的一个区间，一直往后面遍历，实现O(n) 复杂度的一个算法。利用单调性，规避了很多没有必要的枚举行为。这个单调性，并非是递增递减，而是窗口的往后遍历，left 和 right 动起来。 right 则是属于进窗口，根据判断，left 是否需要出窗口。
进窗口
判断
出窗口
（顺序根据题意更改）
2.什么时候用滑动窗口
当遇到需要寻找一个符合条件的子数组，或者是在一段区间找一段连续的区间时，就可以用。
二、题目练习
1、长度最小的子数组
给定一个含有
n个正整数的数组和一个正整数target。找出该数组中满足其总和大于等于target的长度最小的 子数组[numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回0。示例 1：输入：target = 7, nums = [2,3,1,2,4,3] 输出：2
解释：子数组
[4,3]是该条件下的长度最小的子数组。示例 2：输入：target = 4, nums = [1,4,4] 输出：1
示例 3：输入：target = 11, nums = [1,1,1,1,1,1,1,1] 输出：0
思路：
题目要求最短的子数组相加等于target，示例1解释中，[4,3]相加大于等于7，并且是最短长度2，也有其他相加大于等于7的元素，比如[2,3,1,2],但是长度为3，不是最短的。
1.暴力解法：枚举出所有子数组的和 （ O(n^2) ）
定义left，right，sum 全部都加一边，全部都要遍历
2、利用单调性，使用“同向双指针”来优化 （滑动窗口）
在暴力枚举基础上优化，因为累加到大于target之后，right就没有必要往后遍历累加了，此时left 出窗口，就可以缩小区间，sum再减去nums[left],再进行判断，更新结果。
1.left = 0, right = 0;
2. right进窗口
3. 判断
4.更新结果
出窗口
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size(), sum = 0, minlen = INT_MAX;//minlen是后面返回的结果
for (int left = 0, right = 0; right < n; right++)
{
sum += nums[right];//进窗口
while (sum >= target)//判断
{
minlen = min(minlen, right - left + 1);//更新结果
sum -= nums[left++];//出窗口
}
}
return minlen == INT_MAX ? 0 : minlen;
}
};2、无重复字符的最小子串
给定一个字符串
s，请你找出其中不含有重复字符的 最长子串的长度。示例 1:输入: s = "abcabcbb" 输出: 3
解释: 因为无重复字符的最长子串是
"abc"，所以其长度为 3。示例 2:输入: s = "bbbbb" 输出: 1
解释: 因为无重复字符的最长子串是
"b"，所以其长度为 1。示例 3:输入: s = "pwwkew" 输出: 3
解释: 因为无重复字符的最长子串是
"wke"，所以其长度为 3。 请注意，你的答案必须是 子串 的长度，"pwke"是一个子序列，不是子串。
这题做法和上一题基本相同，只是用了哈希表思想，换汤不换药。
第一种写法：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int left = 0, right = 0, n = s.size();
int ret = 0;
int hash[128] = { 0 };
while (right < n)
{
hash[s[right]]++;
while (hash[s[right]] > 1)
hash[s[left++]]--;
ret = max(ret, right - left + 1);
right++;
}
return ret;
}
};
第二种写法：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size(), ret = 0;
int hash[128] = { 0 };
for (int left = 0, right = 0; right < n; right++)
{
hash[s[right]]++;
while (hash[s[right]] > 1)
{
hash[s[left++]]--;
}
ret = max(ret, right - left + 1);ret写在外面，考虑到s = " " 的情况
}
return ret;
}
};3、最大连续1的个数Ⅲ
给定一个二进制数组
nums和一个整数k，如果可以翻转最多k个0，则返回 数组中连续1的最大个数 。示例 1：
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出：6 解释：[1,1,1,0,0,1,1,1,1,1,1]粗体数字从 0 翻转到 1，最长的子数组长度为 6。示例 2：
输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出：10 解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]粗体数字从 0 翻转到 1，最长的子数组长度为 10。
解法思路：
如果按照题目意思来翻转，那么相当麻烦，我们可以正难则反，换成最长区间内0的个数小于等于k，这样的话，又是直接套用滑动窗口的思路。
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
//找出最长的子数组。如果0的个数不超过K个，则全部都可以返回
int ret = 0;//用来计算连续长度，zero用来记0的个数
for (int left = 0, right = 0, zero = 0; right < nums.size(); right++)
{
if(nums[right]== 0) zero++;//进窗口，直接无视1，
while (zero > k)//判断
if(nums[left++] == 0) zero--;//出窗口
ret = max(ret, right - left + 1);//更新结果
//这一步要写在while 外面，因为0001，k = 4，这种情况是进不去while的，就没有办法更新结果
//写在while 里面还是外面，把可能性都列出来，大于等于小于，大概的可能，然后进行分析
}
return ret;
}
};4、将x减到0的最小操作数
给你一个整数数组
nums和一个整数x。每一次操作时，你应当移除数组nums最左边或最右边的元素，然后从x中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。如果可以将
x恰好 减到0，返回 最小操作数 ；否则，返回-1。示例 1：
输入：nums = [1,1,4,2,3], x = 5 输出：2 解释：最佳解决方案是移除后两个元素，将 x 减到 0 。示例 2：
输入：nums = [5,6,7,8,9], x = 4 输出：-1示例 3：
输入：nums = [3,2,20,1,1,3], x = 10 输出：5 解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
正难则反，转化成求中间部分的最大区间，如果没有找到要记录的操作数，就一直找下去。
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int sum = 0;
for (int a : nums) sum += a;//sum 是数组中所有元素的总和
int target = sum - x; //正难则反
//细节问题
if (target < 0) return -1;
int ret = -1;
for (int left = 0, right = 0,tmp = 0; right < nums.size();right++)
{
tmp += nums[right];//进窗口
while (tmp > target)//判断
tmp -= nums[left++];//出窗口
if (tmp == target)//更新结果
ret = max(ret, right - left + 1);
}
if (ret == -1 ) return -1;
else return nums.size() - ret;
}
};5、水果成篮
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组
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] 这两棵树。
示例 4：输入：fruits = [3,3,3,1,2,1,1,2,3,3,4] 输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。
进窗口扔进哈希表来判断这个水果是否存在，不存在的话， kind需要++，在的话，如果kind超过了要求，就需要从左边扔出哈希表，如果次种类已经不存在了，kind需要--。kind 在超过2之前，就已经进行了最长子数组更新。
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int hash[100001] = {0};
int ret = 0, kind = 0, n = fruits.size();
for (int left = 0, right = 0; right < n; right++){
if (hash[fruits[right]] == 0) kind++;//进窗口
hash[fruits[right]]++;
/*if (kind > 2){
hash[fruits[left]]--;//出窗口
if (hash[fruits[left]] == 0) kind--;
left++;
}*/
while (kind > 2)//判断
{
hash[fruits[left]]--;//left种类--，此时left还没有++，
if (hash[fruits[left]] == 0){
kind--;
}
left++;//放在外面++，是因为先判断left是否在hash中，不在的话，kind--，在的话继续出窗口，如果先出了窗口，前面的元素就没有进行判断了，如果连续的两个元素不相同的话，就会出错
}
ret = max (ret , right - left + 1);
}
return ret;
}
};6、找到字符串中所有字母异位词
给定两个字符串
s和p，找到s中所有p的 异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。示例 1:
输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。示例 2:
输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
- 因为字符串 p 的异位词的⻓度⼀定与字符串 p 的⻓度相同，所以我们可以在字符串 s 中构造⼀个⻓度为与字符串 p 的⻓度相同的滑动窗⼝，并在滑动中维护窗⼝中每种字⺟的数量；
- 当窗⼝中每种字⺟的数量与字符串 p 中每种字⺟的数量相同时，则说明当前窗⼝为字符串 p 的异位词；
- 因此可以⽤两个⼤⼩为 26 的数组来模拟哈希表，⼀个来保存 s 中的⼦串每个字符出现的个数，另⼀个来保存 p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ret;
int hash1[26] = { 0 };//统计字符串p中每个字符出现的个数
for (auto ch : p) hash1[ch - 'a']++;
int hash2[26] = { 0 };//统计窗口里面的每个字符出现的个数
int m = p.size();
for (int left = 0, right = 0, count = 0;right < s.size(); right++)
{
char in = s[right];
if (++hash2[in - 'a'] <= hash1[in - 'a']) count++;//进窗口，维护count
if (right - left + 1 > m)//判断
{
char out = s[left++];
if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;//出窗口+维护count
}
//更新结果
if(count == m) ret.push_back(left);
}
return ret;
}
};7、串联所有单词的子串
给定一个字符串
s和一个字符串数组words。words中所有字符串 长度相同。
s中的 串联子串 是指一个包含words中所有字符串以任意顺序排列连接起来的子串。
- 例如，如果
words = ["ab","cd","ef"]， 那么"abcdef"，"abefcd"，"cdabef"，"cdefab"，"efabcd"， 和"efcdab"都是串联子串。"acdbef"不是串联子串，因为他不是任何words排列的连接。返回所有串联子串在
s中的开始索引。你可以以 任意顺序 返回答案。示例 1：输入：s = "barfoothefoobarman", words = ["foo","bar"] 输出：
[0,9]解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。 子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。 子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。 输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2：输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] ，输出：
[]解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。 s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。 所以我们返回一个空数组。
示例 3：输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出：[6,9,12] 解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
如果我们把每⼀个单词看成⼀个⼀个字⺟，问题就变成了找到「字符串中所有的字⺟异位词」。⽆⾮就是之前处理的对象是⼀个⼀个的字符，我们这⾥处理的对象是⼀个⼀个的单词。
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ret;
unordered_map<string, int> hash1; // 保存 words ⾥⾯所有单词的频次
for (auto& s : words) hash1[s]++;
int len = words[0].size(), m = words.size();
for (int i = 0; i < len; i++) // 执⾏ len 次
{
unordered_map<string, int> hash2; // 维护窗⼝内单词的频次
for (int left = i, right = i, count = 0; right + len <= s.size();
right += len)
{
// 进窗⼝ + 维护 count
string in = s.substr(right, len);
hash2[in]++;
if (hash1.count(in) && hash2[in] <= hash1[in]) count++;
// 判断
if (right - left + 1 > len * m)
{
// 出窗⼝ + 维护 count
string out = s.substr(left, len);
if (hash1.count(out) && hash2[out] <= hash1[out]) count--;
hash2[out]--;
left += len;
}
// 更新结果
if (count == m) ret.push_back(left);
}
}
return ret;
}
};8、最小覆盖子串
给定两个字符串
s和t。返回s中包含t的所有字符的最短子字符串。如果s中不存在符合条件的子字符串，则返回空字符串""。如果s中存在多个符合条件的子字符串，返回任意一个。注意： 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'示例 2：
输入：s = "a", t = "a" 输出："a"示例 3：
输入：s = "a", t = "aa" 输出："" 解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。
- 研究对象是连续的区间，因此可以尝试使⽤滑动窗⼝的思想来解决。
- 如何判断当前窗⼝内的所有字符是符合要求的呢？
我们可以使⽤两个哈希表，其中⼀个将⽬标串的信息统计起来，另⼀个哈希表动态的维护窗⼝内字符串的信息。
当动态哈希表中包含⽬标串中所有的字符，并且对应的个数都不⼩于⽬标串的哈希表中各个字符的个数，那么当前的窗⼝就是⼀种可⾏的⽅案
class Solution
{
public:
string minWindow(string s, string t)
{
int hash1[128] = { 0 }; // 统计字符串 t 中每⼀个字符的频次
int kinds = 0; // 统计有效字符有多少种
for (auto ch : t)
if (hash1[ch]++ == 0) kinds++;
int hash2[128] = { 0 }; // 统计窗⼝内每个字符的频次
int minlen = INT_MAX, begin = -1;
for (int left = 0, right = 0, count = 0; right < s.size(); right++)
{
char in = s[right];
if (++hash2[in] == hash1[in]) count++; // 进窗⼝ + 维护 count
while (count == kinds) // 判断条件
{
if (right - left + 1 < minlen) // 更新结果
{
minlen = right - left + 1;
begin = left;
}
char out = s[left++];
if (hash2[out]-- == hash1[out]) count--; // 出窗⼝ + 维护 count
}
}
if (begin == -1) return "";
else return s.substr(begin, minlen);
}
};原文地址：https://blog.csdn.net/2201_75956982/article/details/143833715
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！