【算法专题】滑动窗口类
个人主页：CSDN_小八哥向前冲~
所属专栏：算法基础入门
目录
长度最小的子数组
无重复字符的最长子串
最大连续1的个数
将x减到0的最小操作数
水果成篮
找到字符串中所有字母异位词
最小覆盖字串
长度最小的子数组
题目：【LeetCode】长度最小的子数组
思路：
解法一：暴力枚举，注意，一般不推荐，因为有些题目因为时间效率问题，过不了 oj ！！！
代码：
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size(),len=INT_MAX;for(int i=0;i<n;i++){int sum=0;for(int j=i;j<n;j++){sum+=nums[j];if(sum>=target) len=min(len,j-i+1);}}return len==INT_MAX?0:len;}
};解法二：双指针（滑动窗口）
代码：
class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int sum=0,n=nums.size(),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;}
};无重复字符的最长子串
题目：【LeetCode】无重复字符的最长字串
思路：
代码：
class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128]={0};int n=s.size(),len=0;for(int left=0,right=0;right<n;right++){hash[s[right]]++;while(hash[s[right]]>1)hash[s[left++]]--;len=max(len,right-left+1);}return len;}
};最大连续1的个数
题目：【LeetCode】最大连续1的个数
思路：
代码：
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n=nums.size(),len=0;for(int left=0,right=0,zero=0;right<n;right++){if(nums[right]==0)zero++;while(zero>k){if(nums[left++]==0)zero--;}len=max(len,right-left+1);}return len;}
};
将x减到0的最小操作数
题目：【LeetCode】将x减到0的最小操作数
思路：
如果直接按照题目说的操作，比较难，不好写代码也不好操作，所以我们可以转化成：
在这个数组里面找最大等于某个数的字串。
代码：
class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum1=0;for(auto& e:nums)sum1+=e;int n=nums.size(),target=sum1-x,ret=-1;//细节if(target<0)return -1;for(int left=0,right=0,sum2=0;right<n;right++){sum2+=nums[right];//进窗口while(sum2>target)sum2-=nums[left++];//出窗口if(sum2==target){ret=max(ret,right-left+1);}}return ret==-1?ret:n-ret;}
};水果成篮
题目：【LeetCode】水果成篮
思路：
代码：
class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100000]={0};int n=fruits.size(),ret=0;for(int left=0,right=0,count=0;right<n;right++){if(hash[fruits[right]]==0) count++;//记录有效数字hash[fruits[right]]++;//进哈希while(count>2) //出窗口挪动数据{hash[fruits[left]]--;if(hash[fruits[left]]==0) count--;left++;}ret=max(ret,right-left+1);//更新数据}return ret;}
};找到字符串中所有字母异位词
题目：【LeetCode】找到字符串中所有字母异位词
思路：
代码：
class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[26]={0};//哈希记录p的for(auto& e:p)hash1[e-'a']++;int len=p.size();int hash2[26]={0};int n=s.size(),count=0;//count记录有效字母for(int left=0,right=0;right<n;right++){char in=s[right];if(++hash2[in-'a']<=hash1[in-'a']) count++;//进窗口记录countif(right-left+1>len)//出窗口{char out=s[left++];if(hash2[out-'a']--<=hash1[out-'a']) count--;}if(count==len) ret.push_back(left);//记录下标}return ret;}
};最小覆盖字串
题目：【LeetCode】最小覆盖字串
思路：
代码：
class Solution {
public:string minWindow(string s, string t) {int hash1[128]={0};int kinds=0;for(auto& e:t)if(hash1[e]++==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++;while(count==kinds){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);}
};这些题目你都会了嘛？我们下期见！