滑动窗口问题记录

对于字符串或者数组找到一个连续的区间这个区间满足一定的条件。这样的问题就使用滑动窗口来解决滑动窗口从某种意义上属于动态规划算法也使用了双指针。使用滑动窗口算法有一个基础的前提即数据结构是线性的数据结构。tcp协议栈中发送窗口是滑动窗口也是因为tcp是面向连接的字节流协议有序列号是线性才会有滑动窗口。滑动窗口的关键是确定窗口的两个边沿什么时候移动什么条件下移动在移动的时候做什么。一般情况下窗口右边沿是一直向前移动在移动的过程中根据判断条件来决定左边沿是不是需要移动。每一次循环都要判断右边沿需要做什么左边沿需要做什么。1最小覆盖字符串76. 最小覆盖子串 - 力扣LeetCodeclass 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. 无重复字符的最长子串 - 力扣LeetCodeclass Solution { public: int lengthOfLongestSubstring(string s) { //最基本的方法 //长度从大到小遍历字符串看是不是有重复有重复继续进行 //没有重复直接返回 //滑动窗口 //右边沿直接滑动 //用map保存字符所在的索引如果已经存在了说明重复了移动left int ret 0; int size s.size(); int left 0; int right 0; std::mapchar, 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. 长度最小的子数组 - 力扣LeetCodeclass Solution { public: int minSubArrayLen(int target, vectorint 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; } };