【优先算法】专题——滑动窗口
【优先算法】专题——滑动窗口
一、长度最小的子数组
题目描述：
解法⼀（暴⼒求解）（会超时）：
「从前往后」枚举数组中的任意⼀个元素，把它当成起始位置。然后从这个「起始位置」开始，然 后寻找⼀段最短的区间，使得这段区间的和「⼤于等于」⽬标值。
将所有元素作为起始位置所得的结果中，找到「最⼩值」即可。
代码如下：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
// 记录结果int ret = INT_MAX;
int n = nums.size();
// 枚举出所有满⾜和⼤于等于 target 的⼦数组[start, end]
// 由于是取到最⼩，因此枚举的过程中要尽量让数组的⻓度最⼩
// 枚举开始位置
for (int start = 0; start < n; start++)
{
int sum = 0; // 记录从这个位置开始的连续数组的和
// 寻找结束位置
for (int end = start; end < n; end++)
{
sum += nums[end]; // 将当前位置加上
if (sum >= target) // 当这段区间内的和满⾜条件时
{
// 更新结果，start 开头的最短区间已经找到
ret = min(ret, end - start + 1);
break;
}
}
}
// 返回最后结果
return ret == INT_MAX ? 0 : ret;
}
};解法二：
算法思路：
由于此问题分析的对象是「⼀段连续的区间」，因此可以考虑「滑动窗⼝」的思想来解决这道题。 让滑动窗⼝满⾜：从 i 位置开始，窗⼝内所有元素的和⼩于 target （那么当窗⼝内元素之和 第⼀次⼤于等于⽬标值的时候，就是 i 位置开始，满⾜条件的最⼩⻓度）。
做法：将右端元素划⼊窗⼝中，统计出此时窗⼝内元素的和：
- 如果窗⼝内元素之和⼤于等于 target ：更新结果，并且将左端元素划出去的同时继续判 断是否满⾜条件并更新结果（因为左端元素可能很⼩，划出去之后依旧满⾜条件）
- 如果窗⼝内元素之和不满⾜条件： right++ ，另下⼀个元素进⼊窗⼝。
为何滑动窗⼝可以解决问题，并且时间复杂度更低？
这个窗⼝寻找的是：以当前窗⼝最左侧元素（记为 left1 ）为基准，符合条件的情况。也就是在这道题中，从 left1 开始，满⾜区间和 sum >= target 时的最右侧（记为 right1 ）能到哪⾥。
我们既然已经找到从 left1 开始的最优的区间，那么就可以⼤胆舍去 left1 。但是如果继续像⽅法⼀⼀样，重新开始统计第⼆个元素（ left2 ）往后的和，势必会有⼤量重复 的计算（因为我们在求第⼀段区间的时候，已经算出很多元素的和了，这些和是可以在计算下次区间和的时候⽤上的）。
此时， rigth1 的作⽤就体现出来了，我们只需将 left1 这个值从 sum 中剔除。从 right1 这个元素开始，往后找满⾜ left2 元素的区间（此时 right1 也有可能是满 ⾜的，因为 left1 可能很⼩。 sum 剔除掉 left1 之后，依旧满⾜⼤于等于 target ）。这样我们就能省掉⼤量重复的计算。
这样我们不仅能解决问题，⽽且效率也会⼤⼤提升。 时间复杂度：虽然代码是两层循环，但是我们的 left 指针和 right 指针都是不回退的，两者最多都往后移动 n 次。因此时间复杂度是 O(N) 。
参考代码：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int sum = 0,len = INT_MAX,n = nums.size();
for(int left = 0,right = 0;right < n;right++)
{
sum += nums[right];
while(sum >= target)
{
len = min(len,right - left + 1);
sum -= nums[left++];
}
}
return len == INT_MAX ? 0 : len;
}
};时间复杂度O(N)，空间复杂度O(1)
二、无重复字符的最长子串
题目描述：
本题意思就是找=一段连续的子数组。
解法一（暴力解法）：我们可以把元素放到哈希表里面出现重复值就停止，统计一下长度，再依次枚举。
但是这个算法思路是O(N)
解法二：我们画图分析一下
这里我们可以直接用滑动窗口，我们依旧使用一个哈希表来判断重复值，流程如下：
参考代码如下：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int left = 0,right = 0,n = s.size(),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;
}
};时间复杂度O(N)，空间复杂度也是O(1)
三、最⼤连续 1 的个数 III
题目描述：
题目的意思就是说我们可以把0最多翻转K个，但是如果我们真的去把0翻转为1这样会很麻烦，我们不如直接找出最长的子数组但是0的个数不能超过K个。
解法一（暴力解法）：枚举 + zero 计数器
解法二：
根据如上分析之后，我们可以使用滑动窗口，进窗口：遇到1无视，遇到0计数器(统计子数组0的个数)+1，然后判断计数器是否大于K，大于就出窗口left++如果left等于0计数器需要--，最后更新结果
参考代码如下：
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int right = 0,left = 0,n = nums.size(),zero = 0,ret = 0;
while(right < n)
{
if(nums[right] == 0)
++zero;
while(zero > k)
{
if( nums[left++] == 0)zero--;
}
ret = max(ret,right - left + 1);
++right;
}
return ret;
}
};时间复杂度为O(N)，空间复杂度O(1)
四、水果成蓝
题目描述：
题目的意思转化一下其实就是说：找出一个最长的子数组的长度，子数组中不超过两种类型的水果
解法一：暴力枚举 + 哈希表，一次固定一个数，我们用哈希表来统计水果出现的种类。
解法二：滑动窗口 + 哈希表，分析如下：
参考代码如下：
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int,int>hash;//统计窗口内出现了多少种水果
int ret = 0;
for(int left = 0,right = 0;right < fruits.size();right++)
{
hash[fruits[right]]++;//进窗口
while(hash.size() > 2)
{
hash[fruits[left]]--;//出窗口
if(hash[fruits[left]] == 0)
hash.erase(fruits[left]);
++left;
}
ret = max(ret, right - left + 1);
}
return ret;
}
};时间复杂度为O(N) 空间复杂度O(N)
这里我们运行多次发现这个效率一直很低。
这是因为我们使用了哈希表的原因，我们可以做个小优化就是用数组模拟哈希表，代码如下：
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int hash[100001] = {0};
int ret = 0;
for(int left = 0,right = 0,kinds = 0;right < fruits.size();right++)
{
if(hash[fruits[right]] == 0) ++kinds;//统计种类
hash[fruits[right]]++;//进窗口
while(kinds > 2)
{
hash[fruits[left]]--;//出窗口
if(hash[fruits[left]] == 0) --kinds;
++left;
}
ret = max(ret, right - left + 1);
}
return ret;
}
};这里数组的大小开了10^5因为题目中告诉了我们范围。
时间复杂度为O(N) 空间复杂度O(1)
五、将x减到0的最小操作数
题目描述：
实例二返回的结果就是-1，因为减不到刚好数值为0的元素
解题思路如下：
本题的暴力解法就是如果我们sum> target那么我们的left++如果right返回在依次枚举那不是更小了所以我们的right没必要回去，让right保持不动，然后我们的left如果大于target就出窗口，如果找到区间之和sum等于target就更新结果。
参考代码如下：
class Solution {
public:
int minOperations(vector<int>& nums, int x)
{
int left = 0, right = 0;
int n = nums.size();
int target = 0;
for(int a : nums) target += a;
target = target - x;
int ret = -1;
int sum = 0;
while (right < n)
{
sum += nums[right];//进窗口
while (sum > target && left <= right)
{
sum -= nums[left++];//出窗口
}
if (sum == target)
{
ret = max(ret, right - left + 1);
}
++right;
}
if (ret == -1)
{
return -1;
}
else
{
return n - ret;
}
}
};时间复杂度为O(N) 空间复杂度O(1)
六、找到字符串中所有字母异位词
题目描述：
异位词就是与p里面的字符一样然后是连续的但是顺序可以不一样，找到我们就返回下标即可
思路：我们如何快速判断两个字符串是否是“异位词”我们可以利用哈希，用一个hash1来统计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;
}
};时间复杂度O(N) 空间复杂度O(1)
七、串联所有单词的子串
题目描述：
题目的意思就是说子串中只要包含words就行可以任意顺序，返回下标即可
本题和上题非常相似，不同之处就是哈希表和left与right指针的移动还有滑动窗口执行的次数，所以大致思路和上题差不多，依旧使用哈希表+滑动窗口。
如上我们可以看到紫色、绿色、蓝色的横线可以发现我们的子字符串可以和如上三种情况进行比较是否和words是串联子串，如barfoo 还可以arfoot还可以rfooth所以我们要固定3个数因为题目中说words中所有字符串长度相等。
大概实现思路如下：
本题非常考验我们的容器使用和细节的处理。
参考代码如下：
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words)
{
unordered_map<string,int>hash1;//保存words里面所有单词的频率次
for(auto& s: words) hash1[s]++;
int len = words[0].size(),m = words.size();
vector<int>ret;
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)
{
//进窗口 + 维护 count
string in = s.substr(right,len);
hash2[in]++;
//哈希表里如果没有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;
}
};时间复杂度O(N) 空间复杂度O(1)
八、最小覆盖子串
题目描述：
题目的要求就是我们在s中需要找到含有t中的字符，以如下来说ADOBEC中就是覆盖了t也就是ABC，BECODEBA也是的虽然他有两个B但没事只要不少于t中该字符数量就行题目中说了，CODEBA中也是覆盖了ABC，BANC也是覆盖了ABC我们返回BANC因为它最短，题目说了返回s中涵盖t所有字符的最小子串。
解法一：暴力解法 + 哈希表
我们需要用哈希表统计好字符的频次，我们从A开始找，找到之后left++然后right从left的位置再次开始枚举。
我们如下的图，当我们的left和right符合要求的时候我们的left需要++那么left++有两种情况第一种情况就是left++之后依旧满足条件我们的right不动，如果++之后不满足条件我们这段区间都不满足条件了我们的right也就没有必要返回去继续走过去了，直接向右移动。
那么我们就可以使用同向指针也就是我们的滑动窗口+哈希表。
这里判断，我们需要比较两个哈希表我们可以暴力比较但是效率有点低，我们这里可以做一个小优化，也就是用一个count变量来标记，和我们上面那个count的思路大差不差只不过意义不同。
这里为什么不是判断大于等于是因为当我们的right在第二个B上就重复了因为我们标记的种类，不是个数了，注意这里的判断我们判断的是count是否等于hash1的大小。
参考代码如下：
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;//minlen是字符的长度，begin是子字符串的起始位置
for(int left = 0,right = 0,count = 0;right < s.size();right++)
{
//进窗口 + 维护 count
char in = s[right];
if(++hash2[in] == hash1[in]) ++count;
while(count == kinds)//判断
{
//更新结果
if(right - left + 1 < minlen)
{
minlen = right - left + 1;
begin = left;
}
//出窗口 + 维护 count
char out = s[left++];
if(hash2[out]-- == hash1[out]) -- count;
}
}
if(begin == -1) return "";
else return s.substr(begin,minlen);
}
};时间复杂度O(N) 空间复杂度O(1)
腾讯云开发者
