【滑动窗口】C++高效解决子数组问题
个人主页 ： zxctscl
专栏 【C++】、 【C语言】、 【Linux】、 【数据结构】、 【算法】
如有转载请先通知
文章目录
前言
1 209. 长度最小的子数组
1.1 分析
暴力枚举出所有的子数组和，发现可以利用双指针来解决。
这里双指针是同向的，就能优化为滑动窗口。
(1)先初始化left和right，用left和right来标记这个窗口的左右区间
(2)进窗口
(3)判断决定是否出窗口
1.2 代码
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums)
{
int n=nums.size();
int sum=0,len=INT_MAX;
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;
}
};
2 3. 无重复字符的最长子串
2.1 分析
暴力枚举利用双指针加哈希表：
left在起始位置，right遍历，当字符不在哈希表里，就添加；当字符在时候，right就停止遍历，把此时的字符长度更新一下；再把left移动到与right遍历到相同字符的那个位置的后面一个，然后right再继续移动。
使用滑动窗口来实现：
(1)先初始化left和right，用left和right来标记这个窗口的左右区间
(2)进窗口，让字符进入哈希表
(3)判断：当窗口内出现重复字符出窗口，再从哈希表中删除该字符。
再更新长度
2.2 代码
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
int hash[128]={0};//数组模拟哈希表
int n=s.size();
int ret=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);
}
return ret;
}
};
3 1004. 最大连续1的个数 III
3.1 分析
只要翻转的0个数小于等于k就行。
如果按照题目要求翻转，是比较麻烦的，但可以等价处理为：找一个区间满足0的次数不超过k就行。
也就是找出最长子数组，这个子数组的0不超过k个
解法一：暴力枚举所有子数组，加上一个计数器zero
优化一下
固定left，right向后移动，right遇到0统计一个计数器，计数器等于3时候，停止枚举，就是这个区间最优解。
利用滑动窗口来解决问题：
- 先定义两个指针left=0,right=0
- 进窗口，如果right遇到1，无视；遇到0，zero+1
- 判断：zero>k 就 出窗口
判断完后更新结果
3.2 代码
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int ret=0;
for(int left=0,right=0,zero=0;right<nums.size();right++)
{
if(nums[right]==0)zero++;
while(zero>k)
if(nums[left++]==0)zero--;
ret=max(ret,right-left+1);
}
return ret;
}
};
4 1658. 将 x 减到 0 的最小操作数
4.1 分析
发现既有左边删除，又有右边的的，不好操作，此时可以找一个连续区域，恰好所有元素的和(sum)等于sum-x
- 先定义两个指针left=0,right=0
- 进窗口，sum+=nums[right]
- 判断：sum>target
出窗口：sum-=nums[left]
当sum==target判断完后更新结果
4.2 代码
class Solution {
public:
int minOperations(vector<int>& nums, int x)
{
int sum=0;
for(int a:nums)sum+=a;
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 904. 水果成篮
5.1 分析
题目意思就是：找出一个最长子数组，子数组中不超过两种类型的水果。
解法一：暴力枚举+哈希表：从某一个位置开始，建立一个哈希表，暴力枚举时候，遍历一个放哈希表一个，当表中数据超过2时候，就出现了多余水果，前面的区间就是最优解。
优化：固定一个位置left，right遍历数组放在哈希表中，直到某一个位置，right再向右遍历时候，水果种类就超过2，此时这段区间就是最优解。此时，当left向后移动一位时，种类数目（kinds)可能会出现两种情况：（1）kinds不变，那么right也不变；（2）kinds变小,此时right就可以向右移动
解法二：滑动窗口
- 先定义两个指针left=0,right=0
- 进窗口，遍历数组放哈希表里，哈希表里面放水果种类及对应数量
- 判断：如果哈希表长度大于2而且它对应数量为0时候就出窗口
更新结果
5.2 代码
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;
}
};
6 438. 找到字符串中所有字母异位词
6.1 分析
如何快速判断两个字符串是否是异位词？
两个字符串的构成是一样的，利用哈希表，遍历两个字符串分别放在哈希表中，对比两个哈希表中字符出现的个数是否相等就行，相等就是，反之就不是。
算法：
暴力+哈希表
把p字符串先放入哈希表中，再到s中找相等长度的区间子串放在另一个哈希表中，比较一个，相等就把起始位置放在结果中。
当s中与p等长区间中比较后，不是异位词，此时就把s放在哈希表中的第一个字符删除，再加上区间长度下一个位置字符就行。
p长度为m，hash1记录p的字符情况，hash2记录s中一段区间的字符情况
滑动窗口+哈希表
- 先定义两个指针left=0,right=0
- 进窗口，(哈希表遍历s)hash2[in]++
- 判断：right-left+1>m，就出窗口，再hash1[out]–（对应s中的字符得删除）
当两个哈希表里面存在信息是否一致时候，就更新结果
优化：更新判断条件
利用变量count来统计窗口中有效字符的个数
right遍历时候，c加入哈希表2中，与hash1中c个数相比较，都是1，此时count=1；
right继续向后面移动，遇到c加入hash2中，这个时候hash2中c=2，,比hash1中c=1大，这个时候count不更新；
right继续向后移动，b放入hash2中，比较hash1中b=1，此时count=2，而且s遍历的区间长度等于p的长度，此时有效字符个数count=2不等于p的长度；
right继续右移，这是区间长度大于p的，left就右移，a放到哈希表2中a=1，count=3，删除c（hash2中c=2，删除的这个c是无效字符），hash2中c=1；
进窗口：进窗口后比较hash2[in]<=hash1[in]此时count++;
出窗口：出去前 hash2[out]<=hash1[out]此时count–;
更新结果：count=m
6.2 代码
class Solution {
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> ret;
int hash1[26]={0};//统计p
for(auto x:p)hash1[x-'a']++;
int hash2[26]={0};//s
int m=p.size();
for(int left=0,right=0,count=0;right<s.size();right++)
{
char in=s[right];
hash2[in-'a']++;
if(hash2[in-'a']<=hash1[in-'a'])count++;
if(right-left+1>m)
{
char out=s[left++];
if(hash2[out-'a']<=hash1[out-'a'])count--;
hash2[out-'a']--;
}
if(count==m)ret.push_back(left);
}
return ret;
}
};
7 30. 串联所有单词的子串
7.1 分析
与上面串联所有单词的子串类似，只不过把字符换成字符串，解法类似。
把题目给的words中的字符串看做一个一个整体，像下面这样
与上面不同的是：
（1）哈希表：不能向上面一样用数组来实现，这里存字符串，得用unordered_map<string,int> hash
（2）left与right指针的移动：移动的步长是单词的长度(len)
（3）滑动窗口指向的次数：单词可能是从s的第一个位置开始划分，也可能是第二个位置，也可能是第三个位置：
滑动窗口执行len次
7.2 代码
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words)
{
vector<int> ret;
unordered_map<string,int> hash1;
for(auto& x:words)hash1[x]++;
int len=words[0].size(),m=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);//进窗口+维护count
hash2[in]++;
if(hash2[in]<=hash1[in])count++;
//判断
if(right-left+1>len*m)
{
//出窗口+维护count
string out=s.substr(left,len);
if(hash2[out]<=hash1[out])count--;
hash2[out]--;
left+=len;
}
//更新结果
if(count==m)ret.push_back(left);
}
}
return ret;
}
};
8 76. 最小覆盖子串
8.1 分析
与串联所有单词的子串类似，
解法一：暴力枚举+哈希表
在连续区间中找符合要求的ABC出现次数
在符合连续区间中，left右移right会出现两种情况
解法二：滑动窗口
- 先定义两个指针left=0,right=0
- 进窗口，hash2[in]++
- 判断：对比一下hash2有效字符大于等于hash1有效字符就更新结果起始位置，最短长度；再出窗口，hash2[out]–
优化：利用变量count来统计窗口中有效字符的种类
（1）.进窗口 进之后当hash2[in]==hash1[in]此时count++
（2） 出窗口 出之前，当hash2[out]==hash1[out]，count--
（3）判断 count==hash.size()
8.2 代码
class Solution {
public:
string minWindow(string s, string t)
{
int hash1[128]={0};
int kinds=0;//统计有效字符有多少种
for(auto& x:t)
{
if(hash1[x]==0) kinds++;
hash1[x]++;
}
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];
hash2[in]++;
if(hash2[in]==hash1[in])count++;//进窗口+维护count
while(kinds==count)
{
if(right-left+1<minlen)
{
minlen=right-left+1;
begin=left;
}
char out=s[left++];
if(hash2[out]--==hash1[out])count--;
}
}
if(begin==-1)return "";
else return s.substr(begin,minlen);
}
};
更多推荐
26
0- 0
已为社区贡献2条内容
所有评论(0)