滑动窗口代码模板

代码模板：

//滑动窗口伪代码
class Solution {
public:int minWindow(string s) {// 同方向移动，起始的时候，都位于 0，表示我们定义搜索区间为 [left, right) ，此时区间为空区间int left = 0;int right = 0;while(right < Slen){//每一次循环的开始，都一定不满足条件//（因为上一次循环是从满足条件跳出while的）// 这里对状态做修改，好让程序在后面检测到满足条件right++; //右移right,实际上，这一句也可以写在外层while的最后一句while(满足条件){ // 对状态做修改，好让程序在后面检测到不满足条件left++;     //右移left}//记录当前最接近结果的值}return maxlen;}
};

---

例题1：leecode第3题：无重复字符的最长子串

给定一个字符串 s ，请你找出其中不含有重复字符的 最长
子串
的长度。

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

解答：

class Solution {
public:int lengthOfLongestSubstring(string s) {int len = s.size();if(len < 2){return len;}int *freq = new int[128];for(int i = 0; i < 128; i++){freq[i] = 0;}int maxlen = 1;//维护一个变量用于记录最长字符串的长度int left = 0, right = 0;//循环不变量 [left, right）无重复字符串while(right < len){freq[s[right]]++; // 对状态做修改，好让程序在后面检测到满足条件:[left, right）出现重复元素right++;while(freq[s[right-1]] == 2){//满足条件：[left, right）出现重复元素freq[s[left]]--;left++;     }maxlen = maxlen < (right - left) ? (right - left) : maxlen;//记录当前最接近结果的值}return maxlen;}
};

---

例题2：lecoode第76题：最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

m == s.length
n == t.length
1 <= m, n <= 105
s 和 t 由英文字母组成

进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

解答：

class Solution {
public:string minWindow(string s, string t) {int s_len = s.size();int t_len = t.size();int count = 0;                     //记录t包含的字母个数vector<int> MinWindow(128, 0);     //记录滑动窗口各个字母出现的次数vector<int> CharArray(128, 0);     //记录t包含各个字母出现的次数//记录t每个字母出现的次数for(int i = 0; i < t_len; ++i){++CharArray[t[i]];}//记录t有多少个字母for(int i = 0; i < 128; ++i){if(CharArray[i] > 0){++count;}}int left = 0;               //滑动窗口的左边int right = 0;              //滑动窗口的右边int m_left = 0;             //记录最小子串在s的起始位置int minLen = s_len + 1;     //记录最小子串的长度int sameNumber = 0;         //记录s中与t相同的字母的个数while(right < s_len){char rc = s[right];//这个字母在t中出现if(CharArray[rc] > 0){//将这个字母加入到记录滑动窗口的数组中++MinWindow[rc];//此时这个字母在s出现的次数等于在t出现的次数，即s中这个字母满足覆盖t子串的要求if(MinWindow[rc] == CharArray[rc]){++sameNumber;}}++right;//当s中满足t中所有出现的字母要求while(sameNumber == count){//维护当前最小字符串的起始和偏移if(minLen > right - left){minLen = right - left;m_left = left;}char lc = s[left];//对滑动窗口将要做边界右移会造成的状态进行统计if(CharArray[lc] > 0){--MinWindow[lc];if(MinWindow[lc] < CharArray[lc]){--sameNumber;}}//滑动窗口左边界右移++left;}}//如果没进入sameNumber == count循环，证明s是不满足包含t的条件，则返回空字符串return minLen == 1 + s_len ? "" : s.substr(m_left, minLen);}
};

---

例题3：leecode lcr第8题：长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

解答：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int len = nums.size();//先判断特殊情况，如果数组总和都小于targer，则返回0(即示例3的情况)int sum = 0;for(int i = 0; i < len; i++){sum += nums[i];}if(sum < target) return 0;int WindowSum = 0; //记录当前窗口的元素和int min_len = len; //维护一个最小长度int left = 0, right = 0;while(right < len){WindowSum += nums[right];right++;while(WindowSum >= target){min_len = (min_len < right - left) ? min_len : (right - left);WindowSum -= nums[left];left++;}}return min_len;}
};

---

例题4：leecode 438. 找到字符串中所有字母异位词：（固定窗口大小的滑动窗口问题）

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

1 <= s.length, p.length <= 3 * 104
s 和 p 仅包含小写字母

解答：

class Solution {
public:vector<int> findAnagrams(string s, string p) {int s_len = s.size();int p_len = p.size(); vector<int> res;//记录结果使用if(s_len < p_len) return res;vector<int> freq_p(26, 0);vector<int> window_freq(26, 0);//统计p的频数for(int i = 0; i < p_len; i++){freq_p[p[i] - 'a']++;}//窗口的长度固定为p的长度，并统计窗口在最初始的频数int left = 0, right = p_len - 1;for(int i = 0; i < p_len; i++){window_freq[s[i] - 'a']++;}while(right < s_len - 1 ){int isEq = IsArrEq(window_freq, freq_p);if(isEq){res.push_back(left);}//移动窗口，并统计移动后的频数window_freq[s[left] - 'a']--;left++;window_freq[s[right + 1] - 'a']++;right++;}//跳出循环后，还要单独判断一下移动到s最右侧的情况int isEq = IsArrEq(window_freq, freq_p);if(isEq){res.push_back(left);}return res;}
//此函数用于判断两个频数数组是否相等int IsArrEq(vector<int> arr1, vector<int>arr2){for(int i = 0; i < 26; i++){if(arr1[i] != arr2[i])return 0;}return 1;}
};