滑动窗口问题记录

对于字符串或者数组，找到一个连续的区间，这个区间满足一定的条件。这样的问题就使用滑动窗口来解决，滑动窗口，从某种意义上属于动态规划算法，也使用了双指针。

使用滑动窗口算法有一个基础的前提，即数据结构是线性的数据结构。tcp协议栈中发送窗口是滑动窗口，也是因为tcp是面向连接的字节流协议，有序列号，是线性，才会有滑动窗口。

滑动窗口的关键是确定窗口的两个边沿什么时候移动，什么条件下移动，在移动的时候做什么。一般情况下，窗口右边沿是一直向前移动，在移动的过程中根据判断条件来决定左边沿是不是需要移动。每一次循环都要判断右边沿需要做什么，左边沿需要做什么。

1最小覆盖字符串

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

class Solution { public: string minWindow(string s, string t) { //找一个范围，字符串或者数组，这样的问题，使用滑动窗口 //滑动窗口，关键是窗口的两个边沿什么时候移动 //一般情况下是，一个边沿直接移动 //另外一个在特定条件下移动 //1、首先计算t字符串每个字符出现的次数 //2、然后遍历s字符串，看计数，然后增加count，移动右边沿 //3、什么时候移动左边沿呢，count和t的长度相同的时候，这个字符串就是一个预期的结果 for (char oneC : t) { tCharCount[oneC]++; } int left = 0; int right = 0; for (right = 0; right < s.size(); right++) { sCharCount[s[right]]++; //为什么是<=，而不是<，因为sCharCount[s[right]]在上边已经++了 //循环算法，递归算法，这些都是最基础的算法，关键是在这些算法行进的过程中要做什么事情 if (sCharCount[s[right]] <= tCharCount[s[right]]) { count++; } while (sCharCount[s[left]] > tCharCount[s[left]]) { sCharCount[s[left]]--; left++; } if (count == t.size()) { if (ret.empty() || right - left + 1 < ret.size()) { ret = s.substr(left, right - left + 1); } } } return ret; } int tCharCount[123] = {0}; int sCharCount[123] = {0}; int count = 0; std::string ret = ""; };

2无重复字符的最长子串

3. 无重复字符的最长子串 - 力扣（LeetCode）

class Solution { public: int lengthOfLongestSubstring(string s) { //最基本的方法 //长度从大到小遍历字符串，看是不是有重复，有重复继续进行 //没有重复直接返回 //滑动窗口 //右边沿直接滑动 //用map保存字符所在的索引，如果已经存在了，说明重复了，移动left int ret = 0; int size = s.size(); int left = 0; int right = 0; std::map<char, int> charIndex; for (; right < size; right++) { if (charIndex.find(s[right]) != charIndex.end()) { //这个判断条件很容易忘 if (left < charIndex[s[right]] + 1) { left = charIndex[s[right]] + 1; } } //这行很容易忘 charIndex[s[right]] = right; ret = (right - left + 1) > ret ? (right - left + 1) : ret; } return ret; } };

3长度最小的子数组

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

class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { //右边沿一直向前走 //用一个sum记录和 //当和大于等于target，移动left //ret初始值初始化为0 int len = nums.size(); int left = 0; int right = 0; int sum = 0; int ret = 1000000; for (; right < len; right++) { sum += nums[right]; // >= 而不是 >，因为结果都是在这里计算的 while (sum >= target) { ret = right - left + 1 < ret ? right - left + 1 : ret; sum -= nums[left]; left++; } } return ret == 1000000 ? 0 : ret; } };