发布时间：2025-06-24 20:48:54  作者：北方职教升学中心  阅读量：350

3.跟新状态：在每一步，计算或者更新窗口内的数据，并根据需要更新结果，比如窗口内的大小，最大值，最小值等变量。这些例题也是滑动窗口算法的经典实例。

• 核心思想

  滑动窗口的核心思想是利用窗口的移动来优化问题的求解过程（通过两个指针同行移动其实就是滑动窗口），避免不必要的重复过程，从而提高算法的效率。

• 数据序列(Data Sequence)：滑动窗口在其上进行操作的一系列数据，可以是数组，字符串等。

  2.移动窗口：使用循环遍历数组或者字符串，根据滑动规则逐步移动窗口。

• 窗口位置(Window Position)：由左右边界（也就是两个指针）定义的窗口在数据序列中的当前位置。

  二.例题

  1.长度最小的子数组

  链接：leetcode.209.长度最小的子数组
  题目：

  

  算法原理：

  

  代码实现：

  intminSubArrayLen(inttarget,vector<int>&nums){//滑动窗口算法intleft=0;intright =0;intsum =0;size_t len=0;size_t minlen =-1;//右指针进窗口while(right<nums.size()){sum +=nums[right];//当和大于目标值时就是左指针出窗口if(sum>=target){//注意这里一定是左指针小于等于右指针while(left<=right&&sum>=target){len =right -left +1;if(len<minlen){minlen =len;}sum -=nums[left];left++;}}right++;}returnminlen !=-1?minlen :0;}

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

  链接：leetcode.3.无重复字符的最长子串
  题目：

  

  算法原理：

  

  代码实现：

  intlengthOfLongestSubstring(string s){intleft =0,right =0;intmaxlen =0;//定义一个set类型的哈希表unordered_set<char>hash;while(right<s.size()){//进窗口pair<unordered_set<char>::iterator,bool>p=hash.insert(s[right]);//当插入失败时，也就是遇到重复字符if(p.second==false){//出窗口，移动左指针找到重复的字符位置，移动加删除while(s[left]!=*(p.first)){hash.erase(s[left++]);}//当找到重复的字符时，删除左指针指向的该字符，插入右指针指向的该字符hash.erase(s[left++]);hash.insert(s[right]);}//更新最长字串的长度maxlen =max(maxlen,right -left +1);right++;}returnmaxlen;}

  3.最大连续一的个数

  链接：leetcode.1004.最大连续一的个数
  题目：

  

  算法原理：

  

  代码实现：

  intlongestOnes(vector<int>&nums,intk){//定义左右指针intleft =0,right =0;intmaxlen =0;intzero =0;while(right<nums.size()){if(nums[right]==0){zero++;}if(zero>k){while(nums[left]){left++;}zero--;left++;}maxlen =max(maxlen,right -left +1);right++;}returnmaxlen;}

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

  链接：leetcode.1658.将x减到0的最小操作数
  题目：

  

  算法原理：

  

  代码实现：

  intminOperations(vector<int>&nums,intx){//计算数组总和intcount =0;for(autoe :nums){count +=e;}//目标值等于数组总和减去xinttarget =count -x;//当出现特殊情况，就是目标值等于0，说明减去整个数组，直接返回数组长度，就是最小操作数if(target==0){returnnums.size();}intsum =0;intleft =0,right =0;intmaxlen =0;while(right<nums.size()){//进窗口sum +=nums[right];//当子数组和大于目标值时，出窗口if(sum>target){while(left<right&&sum>target){sum -=nums[left++];}}//当等于目标值时，就是要找的子数组，计算子数组长度并更新sum值if(sum==target){maxlen =max(maxlen,right -left +1);sum -=nums[left++];}right++;}//如果最大数组长度不为0，最小操作数就是数组长度减去最大数组长度intminoperations=-1;if(maxlen){minoperations =nums.size()-maxlen;}returnminoperations;}

  5.水果成篮

  链接：leetcode.904.水果成篮
  题目：

  

  算法原理：

  

  代码实现：

  inttotalFruit(vector<int>&fruits){unordered_map<int,int>hash;intleft =0,right =0;intmaxlen =0;//记录哈希桶的个数intbucket =0;while(right <fruits.size()){// 进窗口，移动右指针hash[fruits[right]]++;//当某元素第一次插入时，桶的个数加一if(hash[fruits[right]]==1){bucket++;}//当桶的个数大于二时，水果种类超过三种，要移除一种if(bucket >2){//出窗口，直到桶的个数，也就是水果种类小于等于2while(left <right &&bucket >2){hash[fruits[left]]--;if(hash[fruits[left]]==0){hash.erase(fruits[left]);bucket--;}left++;}}//更新子数组的最大长度maxlen =max(maxlen,right -left +1);right++;}returnmaxlen;}

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

  链接：leetcode.438.找到字符串中所有字母异位词
  题目：

  

  算法原理：

  

  代码实现：

  vector<int>findAnagrams(string s,string p){//定义两个哈希表分别用来存储两个字符串,建立字符和字符个数的映射关系unordered_map<char,int>hashs;unordered_map<char,int>hashp;//定义一个数组用来存储结果vector<int>v;//定义左右指针intleft=0,right=0;//定义一个变量用来记录字符的有效个数intcount =0;for(autoe :p){hashp[e]++;}while(right<s.size()){//进窗口hashs[s[right]]++;//如果哈希表s中存放字符个数小于哈希表p中的个数，count加一if(hashs[s[right]]<=hashp[s[right]]){count++;}//判断条件if(right-left+1>p.size()){//出窗口if(hashs[s[left]]<=hashp[s[left]]){count--;}hashs[s[left]]--;if(hashs[s[left]]==0){hashs.erase(s[left]);}left++;}//更新结果if(count==p.size()){v.push_back(left);}right++;}returnv;}

  7.串联所有单词的子串

  链接：leetcode.30.串联所有单词的字串
  题目：

  

  算法原理：

  

  代码实现：

  vector<int>findSubstring(string s,vector<string>&words){// 定义两个哈希表用来存储字符串，建立字符串和个数之间的映射关系unordered_map<string,int>hashs;unordered_map<string,int>hashw;vector<int>v;for(autoe :words){hashw[e]++;}intleft =0,right =0;intcount =0;// len是words数组中每个单词的长度intlen =words[0].size();intsize =words[0].size();// pr字符串是右指针移动区间的字符串，pl字符串是左指针移动区间的字符串string pr;string pl;while(size--){while(right <s.size()){// 进窗口，每次获取len长度的字符串pr.clear();while(len &&len--){pr +=s[right++];}hashs[pr]++;len =words[0].size();if(hashs[pr]<=hashw[pr]){// 有效字符串的个数加一count++;}// 判断条件if((right -left)>len *words.size()){// 左指针移动，获取len长度的字符串pl.clear();while(len &&len--){pl +=s[left++];}if(hashs[pl]<=hashw[pl]){count--;}hashs[pl]--;if(hashs[pl]==0){hashs.erase(pl);}len =words[0].size();}// 更新结果if(count ==words.size()){v.push_back(left);}}left =right =words[0].size()-size;count =0;hashs.clear();}returnv;}

  8.最小覆盖子串

  链接：leetcode.76.最小覆盖子串
  题目：

  

  算法原理：

  

  代码实现：

  string minWindow(string t,string s){// 定义两个哈希表，用来建立字符和个数之间的映射关系unordered_map<char,int>hasht;unordered_map<char,int>hashs;// 将字符串t的字符映射到哈希表t中intbucket =0;for(autoe :t){hasht[e]++;// 统计哈希表t的字符种类if(hasht[e]==1){bucket++;}}// 定义左右指针，count变量记录哈希表s中的字符种类，有效字符个数intleft =0,right =0;intcount =0;// begin字串的起始位置，用来更新结果，minlen记录最小字串的长度intbegin =-1;intminlen =INT_MAX;while(right <s.size()){// 进窗口hashs[s[right]]++;// 两个哈希表中的字符映射关系相等时，count加一if(hashs[s[right]]==hasht[s[right]]){count++;}// 判断条件，字符种类相等while(count ==bucket){// 更新结果minlen =min(minlen,right -left +1);if(minlen ==right -left +1){begin =left;}// 出窗口if(hashs[s[left]]==hasht[s[left]]){count--;}hashs[s[left]]--;if(hashs[s[left]]==0){hashs.erase(s[left]);}left++;}right++;}// 如果没有找到，begin还是初始值返回空字符串，否则返回字串returnbegin ==-1?"":s.substr(begin,minlen);}

  以上就是关于滑动窗口算法的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！