一文带你学会使用滑动窗口

​

​

🔥个人主页：guoguoqiang. 🔥专栏：leetcode刷题

​

​ 209.长度最小的子数组

求最短长度之和等于目标值。
方法一： 暴力枚举（会超时）
从头开始遍历直到之和等于target然后更新结果。这里就不写代码了。
方法二： 滑动窗口

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n=nums.size(),sum=0,len=INT_MAX;for(int left=0,right=0;right<n;right++){sum+=nums[right];//入窗口while(sum>=target){//判断 题目要求就为sum大于等于target然后长度最小len=min(len,right-left+1);//更新结果sum-=nums[left++];//出窗口}}return len==INT_MAX?0:len;//如果它还未更新就说明和没有大于target否则就更新了len。}
};

3.无重复字符的最长字串

可以看出这道题目全是字母，可以通过数组来模拟哈希表
方法一：哈希表+暴力枚举
每有一个就入哈希表，然后就判断是否重复，然后更新结果。循环结束最后的len即为结果

class Solution {
public:int lengthOfLongestSubstring(string s) {int ret = 0; // 记录结果int n = s.length();// 1. 枚举从不同位置开始的最⻓重复⼦串// 枚举起始位置for (int i = 0; i < n; i++) { // 创建⼀个哈希表，统计频次int hash[128] = {0};// 寻找结束为⽌for (int j = i; j < n; j++) {hash[s[j]]++;       // 统计字符出现的频次if (hash[s[j]] > 1) // 如果出现重复的break;// 如果没有重复，就更新 retret = max(ret, j - i + 1);}}// 2. 返回结果return ret;}
};

方法二：
通过哈希表+滑动窗口

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128]={0};int left=0,right=0,n=s.size();int ret=0;while(right<n){//遍历字符串hash[s[right]]++;//进窗口while(hash[s[right]]>1)//判断是否出现重复字符串hash[s[left++]]--;//将这个左对应的元素出窗口ret=max(ret,right-left+1);//更新结果求最长长度right++;//让下一个元素进窗口}return ret;}
};

1004. 最大连续1的个数 III

利用滑动窗口来：
这个题就是记录最大连续1的个数，然后用一个变量来记录0的个数如果大于k就将左侧的元素出窗口直到zero<k;然后更新结果

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++;//记录0的个数while(zero>k){//如果0的个数大于kif(nums[left++]==0) zero--;//就判断left位置是否为0（为0就跳出窗口），不为0就遍历下一个}ret=max(ret,right-left+1);//更新结果}return ret;}
};

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

方法： 滑动窗口
这个相减为最小生成数，然后可以改为中间部分的和为sum-x求长度最长，数组长度-len即为外部相减为0的最短长度。

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum=0;for(auto num:nums) sum+=num;//求全部的和int target=sum-x;//为中间区域的和，这个就可以改为之前的那个最长长度和为targetif(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){//判断是否大于targettmp-=nums[left++];//出窗口}if(tmp==target)//如果和等于targetret=max(ret,right-left+1);//更新结果}if(ret==-1) return ret;//说明没找到else return nums.size()-ret;//就返回n-ret的即为能减为0的最短长度}
};

904.水果成篮

这个题目可以理解为最多只能能摘两种水果，但是不限制数量，所以需要求可以摘的水果的最大数量。
方法： 通过哈希表+滑动窗口来实现

class Solution {
public:int totalFruit(vector<int>& f) {unordered_map<int,int> hash;//创建哈希表int ret=0;for(int left=0,right=0;right<f.size();right++){hash[f[right]]++;//入窗口while(hash.size()>2){//如果种类大于两种，就从左面出窗口，直到种类等于两种hash[f[left]]--;if(hash[f[left]]==0) hash.erase(f[left]);//如果这个种类数量等于零就从哈希表中删除left++;}ret=max(ret,right-left+1);//更新结果}return  ret;}
};

通过观察这个题的数字范围是1到100000 ，可以通过创建一个数组来代替哈希表实现

class Solution {
public:int totalFruit(vector<int>& fruits) {int hash[100001]={0};//哈希表int n=fruits.size();int ret=0;for(int left=0,right=0,kinds=0;right<n;right++){if(hash[fruits[right]]==0) kinds++;//如果这个元素为0说明是新种类，kinds++hash[fruits[right]]++;//进窗口while(kinds>2){hash[fruits[left]]--;//出窗口if(hash[fruits[left]]==0) kinds--;//如果这个值变为零，就需要将种类--；left++;//left++遍历下一个left对应元素，直到种类等于2}ret=max(ret,right-left+1);//更新结果}return ret;}
};

438.找到字符串中所有字母异位词

方法一：暴力枚举+哈希表
就是遍历整个s然后找出等于hash表中p的单词然后就记录到结果中
方法二：滑动窗口+哈希表

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[26]={0};for(auto ch:p) hash1[ch-'a']++;//记录p中的字母int hash2[26]={0};int m=p.size();//记录p中的个数for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];if(++hash2[in-'a']<=hash1[in-'a']) count++;//判断进窗口的元素是否为有效元素if(right-left+1>m){//长度大于m出窗口char out=s[left++];if(hash2[out-'a']--<=hash1[out-'a']) count--;//判断是否为有效元素然后出窗口更新}if(count==m) ret.push_back(left);//更新结果}return ret;}
};

这个题目的范围只包括小写字母，就可以通过一个int数组来代替哈希表。

30.串联所有单词的字符

这个题目说明可以看例子了解：
就是将words中的字符可以全排列找到，然后返回首元素在s中出现的下标位置。

方法一：暴力枚举+哈希表（会超时）
先将words中的元素进哈希表，hash<string,int>统计words中的元素。
然后for循环遍历字符串，判断是否为串联子串。
方法二： 滑动窗口+哈希表
在暴力枚举中是一个单位一个单位进行移动，在这个题中就显得不是很合适，这个我们可以把后面words中的word看作一个单位，按这个单位长度进行移动。这样我们这个题就可以看作找到字符串中所有字母的异位词。
我们需要注意 窗口执行的次数。

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string,int> hash1 ;//将所有的words进入哈希表for(auto& word:words) hash1[word]++;int size=words.size();//记录words中的元素个数int len=words[0].size();//记录words中的单个元素长度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){//一次跳过长度个长度string in=s.substr(right,len);hash2[in]++;//记录s中的单词if(hash1.count(in)&&hash2[in]<=hash1[in])count++;//如果words中存在则进行判断s中出现的次数是不是小于等于words中的if(right-left+1>size*len){//长度超了需要出窗口string out=s.substr(left,len);if(hash1.count(out)&&hash2[out]<=hash1[out]) count--;//出窗口并记录counthash2[out]--;//将这个元素从哈希表中出去left+=len;//一次len个单位长度}if(count==size) ret.push_back(left);//更新结果}}return ret;}
};