当前位置：首页 > news >正文

算法思想总结：滑动窗口算法

news 来源：原创 2024/5/16 14:15:22

创作不易，感谢三连

一.长度最小的数组

. - 力扣（LeetCode）长度最小的数组

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int len=INT_MAX,n=nums.size(),sum=0;//len必须要给一个很大的数，否则for(int left=0,right=0;right<n;++right){sum+=nums[right];//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]={};//计数int len=0, n=s.size();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 len=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;//出窗口len=max(len,right-left+1); }return len;}
};

四.将x减到0的最小操作数

. - 力扣（LeetCode）将x减到0的最小操作数

class Solution {
public:int minOperations(vector<int>& nums, int x) {//将问题转化为求一个最长子数组 其大小正好==sum-xint ret=-1;int sum=accumulate(nums.begin(),nums.end(),0);//计算数组的总和int target=sum-x;//记录目标值if(target<0) return -1;//细节处理for(int left=0,right=0,temp=0,n=nums.size();right<n;++right){temp+=nums[right];//进窗口while(temp>target)  temp-=nums[left++];//出窗口if(temp==target)   ret=max(ret,right-left+1);//更新结果}return ret==-1?-1:nums.size()-ret;}
};

五.水果成篮

. - 力扣（LeetCode）水果成篮

class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001]={0};int ret=0,n=fruits.size();for(int left=0,right=0,kinds=0;right<n;++right){if(hash[fruits[right]]++==0) ++kinds;//进窗口while(kinds>2)  if(--hash[fruits[left++]]==0) --kinds;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(char 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)//count用来记录有效字符的个数{if(++hash2[s[right]-'a']<=hash1[s[right]-'a'])  ++count;//进窗口的同时统计有效字符个数if(right-left+1>m)//判断  出窗口{if(hash2[s[left]-'a']--<=hash1[s[left]-'a'])  --count;++left;}if(count==m) ret.push_back(left);}return ret;}
};

七.最小覆盖字串

. - 力扣（LeetCode）最小覆盖字串

class Solution {
public:string minWindow(string s, string t) {int hash1[128]={0};//统计t字符串个元素的出现次数int kinds=0;//用来统计种类for(char ch:t) if(hash1[ch]++==0)  ++kinds;int hash2[128]={0};//统计s字符串中滑动窗口的元素出现次数int begin=-1,minlen=INT_MAX;//用来记录返回值情况for(int left=0,right=0,count=0;right<s.size();++right){if(++hash2[s[right]]==hash1[s[right]])  ++count;//进窗口的同时统计窗口内元素种类while(count==kinds)//当种类都一样时，可以去更新结果{if(right-left+1<minlen)//因为还需要更新begin，所以不能直接用min{minlen=right-left+1;begin=left;}if(hash2[s[left]]--==hash1[s[left]]) --count;++left;}}return begin==-1?"":s.substr(begin,minlen);}
};