✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：c++篇–CSDN博客
文章目录
- 一.滑动窗口算法
- 二.例题
- 1.长度最小的子数组
- 2.无重复字符的最长字串
- 3.最大连续一的个数
- 4.将x减到0的最小操作数
- 5.水果成篮
- 6.找到字符串中所有字母异位词
- 7.串联所有单词的子串
- 8.最小覆盖子串
一.滑动窗口算法
滑动窗口算法(Sliding Window Algorithm)是一种用于解决数组和字符串相关问题的常用算法。
-
核心思想
滑动窗口的核心思想是利用窗口的移动来优化问题的求解过程（通过两个指针同行移动其实就是滑动窗口），避免不必要的重复过程，从而提高算法的效率。它通过维护一个滑动窗口（窗口大小可变），也就是两个通向移动的指针再数组或者字符串上移动，比根据问题的要求进行相应的操作。
-
关键参数
- 窗口大小
(Window Size)：滑动窗口的宽度，决定了窗口中包含的元素个数。 - 窗口位置
(Window Position)：由左右边界（也就是两个指针）定义的窗口在数据序列中的当前位置。 - 滑动步长
(Slide Step)：每次移动窗口时跨越的数据单位数量。 - 数据序列
(Data Sequence)：滑动窗口在其上进行操作的一系列数据，可以是数组，字符串等。
- 窗口大小
-
算法流程
1.初始化窗口：确定窗口的起始位置和结束位置，通常是数组或者字符串的开头或者任意位置。根据问题要求，确定窗口的大小和滑动规则。
2.移动窗口：使用循环遍历数组或者字符串，根据滑动规则逐步移动窗口。通常是右指针进窗口，左指针出窗口。
3.跟新状态：在每一步，计算或者更新窗口内的数据，并根据需要更新结果，比如窗口内的大小，最大值，最小值等变量。
4.结束条件：当窗口的结束位置达到数组或者字符串的末尾时，算法结束。
接下来通过一些例题来讲解如何使用滑动窗口算法。这些例题也是滑动窗口算法的经典实例。
二.例题
1.长度最小的子数组
链接：leetcode.209.长度最小的子数组
题目：
算法原理：
代码实现：
int minSubArrayLen(int target,vector<int>& nums){//滑动窗口算法int left=0;int right = 0;int sum = 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++;}return minlen != -1 ? minlen : 0;
}
2.无重复字符的最长字串
链接：leetcode.3.无重复字符的最长子串
题目：
算法原理：
代码实现：
int lengthOfLongestSubstring(string s) {int left = 0, right = 0;int maxlen = 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++;}return maxlen;
}
3.最大连续一的个数
链接：leetcode.1004.最大连续一的个数
题目：
算法原理：
代码实现：
int longestOnes(vector<int>& nums,int k){//定义左右指针int left = 0, right = 0;int maxlen = 0;int zero = 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++;}return maxlen;
}
4.将x减到0的最小操作数
链接：leetcode.1658.将x减到0的最小操作数
题目：
算法原理：
代码实现：
int minOperations(vector<int>& nums,int x){//计算数组总和int count = 0;for(auto e : nums){count += e;}//目标值等于数组总和减去xint target = count - x;//当出现特殊情况，就是目标值等于0，说明减去整个数组，直接返回数组长度，就是最小操作数if(target==0){return nums.size();}int sum = 0;int left = 0, right = 0;int maxlen = 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，最小操作数就是数组长度减去最大数组长度int minoperations=-1;if(maxlen){minoperations = nums.size() - maxlen;}return minoperations;
}
5.水果成篮
链接：leetcode.904.水果成篮
题目：
算法原理：
代码实现：
int totalFruit(vector<int> &fruits)
{unordered_map<int, int> hash;int left = 0, right = 0;int maxlen = 0;//记录哈希桶的个数int bucket = 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++;}return maxlen;
}
6.找到字符串中所有字母异位词
链接：leetcode.438.找到字符串中所有字母异位词
题目：
算法原理：
代码实现：
vector<int> findAnagrams(string s,string p){//定义两个哈希表分别用来存储两个字符串,建立字符和字符个数的映射关系unordered_map<char, int> hashs;unordered_map<char, int> hashp;//定义一个数组用来存储结果vector<int> v;//定义左右指针int left=0,right=0;//定义一个变量用来记录字符的有效个数int count = 0;for(auto e : 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++;}return v;
}
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 (auto e : words){hashw[e]++;}int left = 0, right = 0;int count = 0;// len是words数组中每个单词的长度int len = words[0].size();int size = 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();}return v;
}
8.最小覆盖子串
链接：leetcode.76.最小覆盖子串
题目：
算法原理：
代码实现：
string minWindow(string t, string s)
{// 定义两个哈希表，用来建立字符和个数之间的映射关系unordered_map<char, int> hasht;unordered_map<char, int> hashs;// 将字符串t的字符映射到哈希表t中int bucket = 0;for (auto e : t){hasht[e]++;// 统计哈希表t的字符种类if (hasht[e] == 1){bucket++;}}// 定义左右指针，count变量记录哈希表s中的字符种类，有效字符个数int left = 0, right = 0;int count = 0;// begin字串的起始位置，用来更新结果，minlen记录最小字串的长度int begin = -1;int minlen = 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还是初始值返回空字符串，否则返回字串return begin == -1 ? "" : s.substr(begin, minlen);
}
以上就是关于滑动窗口算法的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！
