【看海的算法日记✨优选篇✨】第二回：流动之窗，探索算法的优雅之道
🌈 个人主页：谁在夜里看海.
⛰️ 道阻且长，行则将至
目录
一、算法思想
上一章我们介绍了双指针的算法思想，其核心原理是利用两个指针在数组中移动，以高效解决一个涉及有序序列、子区间的问题。我们主要介绍的是用于解决在有序区间中判断元素对的场景，即判断两个指针指向的元素，并利用序列的单调性完成指针的移动。
我们今天要讲的滑动窗口本质是双指针算法的特化，它与上一章所讲的双指针有所区别：
| 特性 | 双指针 | 滑动窗口 |
| 移动方向 | 两个指针可以同向移动或对向移动 | 只能同向移动，窗口随之调整 |
| 窗口特性 | 不一定维护特定的窗口，只关注指针的状态 | 维护一个动态窗口，用于表示当前连续区间 |
| 使用场景 | 常用于查找元素对，判断满足条件 | 常用于处理连续子数组或子字符串的问题 |
| 条件变化 | 两个指针的关系由问题决定，没有固定结构 | 窗口大小动态变化，与目标条件有关 |
双指针
滑动窗口
在每次调整窗口后，判断窗口是否满足条件，如果能满足，更新结果以记录最优解。
只看算法原理可能又有些抽象，下面看看具体的使用场景：
二、具体运用
1.⻓度最⼩的⼦数组
难度等级：⭐⭐⭐⭐
题目链接：209. 长度最小的子数组 - 力扣（LeetCode）
题目描述：
给定一个含有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
算法思路
暴力枚举：
这道题目的暴力枚举思路是，把每一个区间都枚举出来，筛选出元素总和满足条件的，然后再进一步筛选区间长度最短的，就是最终结果。枚举全部区间我们首先想到的是用两层for循环，但那样时间复杂度太高了，所以我们选择用双指针进行优化：定义left、right指针，用指针的移动完成对数组的遍历。
遍历的过程为：固定left指针为区间的起始位置，right向后一次遍历，枚举出当前起始位置下的所有区间，这里我们要想一个问题，right指针需要将所有元素都遍历一遍吗？并不需要，我们可以在right遍历的过程中，实时地记录当前区间元素和，当元素和>target（满足条件）时，right就不需要要继续遍历了，因为题目要求的是区间长度最小的，再遍历下去长度只会增大。于是我们的滑动窗口思想就产生了：
滑动窗口：
延续上面的思路，固定left作为区间起始位置，right在遍历的过程中找到当前起始位置下满足题目条件（区间元素和>target）的情况时停止遍历，那么接下来应该怎么做呢？移动left指针，修改区间的起始位置，right指针需要从起始位置开始重新遍历吗？并不需要，移动left指针之前我们找的的区间是刚好满足题目条件的情况，此时移动left指针，区间元素减少，那么这一段区间肯定都是不满足条件的，所以right指针不需要回到起始位置，从当前位置继续向后遍历即可。
算法流程
①：定义left、right指针，初始都指向数组首元素；
②：固定left指针，作为区间起始位置，right从起始位置开始向后遍历，遍历的过程中记录区间内元素总和，当元素总和>target时，停止遍历，记录当前区间长度；
③：移动left指针，改变区间起始位置，right不需要回到起始位置，直接从当前位置向后遍历，后续操作与步骤②一样；
④：最后找到满足条件的最短区间情况。
代码
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int left = 0,right = 0,sum = nums[right],len = INT_MAX; while(right<nums.size()) { if(sum<target) { ++right; if(right<nums.size()) sum+=nums[right]; } else { if(left == right) return 1; len = min(len,right-left+1); sum-=nums[left]; ++left; } } return len == INT_MAX ? 0:len; } };
可以看到我们的时间复杂度是非常优秀的
2.最⼤连续1的个数III
难度等级：⭐⭐⭐⭐
题目链接：1004. 最大连续1的个数 III - 力扣（LeetCode）
题目描述：
给定一个二进制数组nums和一个整数k，如果可以翻转最多k个0，则返回 数组中连续1的最大个数 。
示例 1：输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2 输出：6 解释：[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3 输出：10 解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 10。
算法思路
这道题也是让我们找一个满足条件的区间，与上一题类似，有了上一题的铺垫，这道题我们直接从滑动窗口的思想入手：
首先我们还是确定区间起始位置，下一步需要考虑是right遍历的终止情况，即right何时停止遍历。题目让我们找的是连续1的最长区间，并且告诉我们，区间内允许出现k个0元素，所以我们right终止遍历的情况就是：遇到0元素且翻转次数k用完，此时就是当前起始位置下的最长区间。
后面的操作就是移动left指针，修改区间起始位置，那么left是移动一次吗？并不是，如果只移动一次，并不能支持right向后遍历，因为k没有增加，而right当前指向的是0元素，所以left需要一直移动直到将一个0元素“挤出”区间，此时k才会增加，right才能继续遍历。
算法流程
①：初始化left、right指针，指向数组首元素；
②：固定left，作为区间起始位置，right向后遍历，并实时记录当前k的使用情况，遇到0时k--，当k减到0时并且right来到下一个0元素之前，停止遍历，记录当前区间长度；
③：移动left，修改区间起始位置，left需要排出一个0元素方可停止移动，然后right继续遍历；
④：最后找到满足条件的最长区间。
代码
class Solution { public: int longestOnes(vector<int>& nums, int k) { int left = 0,right = 0,flag = k,num = 0,ret = 0; for(right;right<nums.size();++right) { // 为1,继续遍历 if(nums[right]) { ++num; ret = max(num,ret); } // 为0,减小计数 else { --flag; if(flag>=0) { ++num; ret = ret>num?ret:num; continue; } // 计数用完，移动left直到跳过一个0，返还一个计数 while(nums[left]) { ++left;--num; } ++left;++flag; } } return ret; } };
3.⽔果成篮
难度等级：⭐⭐⭐⭐
题目描述：
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组fruits表示，其中fruits[i]是第i棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组fruits，返回你可以收集的水果的 最大 数目。
示例 1：输入：fruits = [1,2,1] 输出：3 解释：可以采摘全部 3 棵树。
示例 2：输入：fruits = [0,1,2,2] 输出：3 解释：可以采摘 [1,2,2] 这三棵树。 如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
算法思路
题目描述很长，简单概括一下就是：在数组中找到一个连续区间，区间内只能包含两种元素，筛选出满足条件的最长区间。
既然是寻找连续区间，那还是用滑动窗口进行解决：
首先依旧是固定区间起始位置，用right指针向后遍历，遍历的终止情况是，区间内已经包含两种元素，并且right位置的下一个元素是第三种元素，我们可以用一个type变量监控当前区间的元素种类
然后是left的移动，修改区间起始位置，同样地left的移动需要将一种元素全部“排除”区间，使type+1，right方可继续遍历。
算法流程
①：初始化left、right，指向数组首元素；
②：固定left，作为区间起始位置，right向后遍历，遇到一种新元素，type--，直到type减到0并且right来到下一种元素前一个位置；
③：移动left，修改区间起始位置，left的移动需要排出全部的一种元素，right才能继续遍历；
④：最终筛选出满足条件的最长区间。
代码
class Solution { public: int totalFruit(vector<int>& fruits) { int left = 0,right=0,hash[100000]={0},type=0,ret=0; while(right<fruits.size()) { if(hash[fruits[right]]==0) ++type; ++hash[fruits[right]];++right; if(type == 3) { ret=max(ret,right-left-1); // 移动窗口 直到type-1 while(type == 3) { --hash[fruits[left]]; if(!hash[fruits[left]]) --type; ++left; } } } if(type==1) return fruits.size(); if(type==2) return max(ret,right-left); return ret; } };
4.串联所有单词的⼦串
难度等级：⭐⭐⭐⭐⭐
题目链接：30. 串联所有单词的子串 - 力扣（LeetCode）
题目描述：
给定一个字符串s和一个字符串数组words。words中所有字符串 长度相同。
s中的 串联子串 是指一个包含words中所有字符串以任意顺序排列连接起来的子串。例如，如果words = ["ab","cd","ef"]， 那么"abcdef"，"abefcd"，"cdabef"，"cdefab"，"efabcd"， 和"efcdab"都是串联子串。"acdbef"不是串联子串，因为他不是任何words排列的连接。
返回所有串联子串在s中的开始索引。你可以以 任意顺序 返回答案。
示例 1：输入：s = "barfoothefoobarman", words = ["foo","bar"] 输出：[0,9]解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。 子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。 子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。 输出顺序无关紧要。返回 [9,0] 也是可以的。
算法思路
题目的要求是让我们在字符串中寻找一个连续区间， 区间内包含数组words中的全部字符串，找到满足条件的所有区间。
我们定义一个哈希表，用来存储数组words中的全部字符串，并定义一个count，用于记录区间内还需要包含元素的个数。right向后遍历一个字符串时，对该字符串进行判断，如果存在于哈希表中，--count。当前遍历的字符串不存在哈希表中时，需要终止遍历，当count减到0时，记录当前区间起始位置；
对于left的移动，我们需要分为两种情况讨论：
①：left==right，说明区间内部不包含元素，需要同时移动left与right
②：left<right，由于right遍历时，只有当前字符串存在于哈希表中，才会继续遍历，这样就保证了区间内元素都是符合条件的，所以此时left只需要向后移动排除一个字符串，count++，支持right继续向后遍历。
注意：
上述思路是存在缺陷的，因为left和right都是以字符串的长度向后遍历的，并不是依次遍历，所以这个过程会遗漏很多情况，我们需要考虑到这些情况，解决办法就是：对区间起始位置加上一个偏移量，如果字符串长度为3，那偏移量范围就是0~2
算法流程
①：初始化left、right，初始值为0+偏移量；
②：固定left，作为区间首元素，left以字符串长度向后遍历，判断当前字符串是否存在哈希表中，如果存在，count--；如果不存在，移动left，修改区间。当count减到0时，记录当前区间起始位置，并移动left，修改区间；
③：移动left分为两种情况：
a.left==right，说明区间为空，left和right同时向后移动；
b.left<right，说明区间存在元素，left向后移动一个字符串，count--，当前位置作为区间起始位置，right继续向后变量。
④：找到满足条件的所有区间。
代码
class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { unordered_map<string,int> hash; for(auto it:words) ++hash[it]; int len = words[0].size(); vector<int> ret; for(int i = 0;i<len;++i) { unordered_map<string,int> target = hash; int left = i,right = i; int count = words.size(); while(right<s.size()) { string cur = s.substr(right,len); if(target.count(cur) && target[cur]>0) { --target[cur]; --count; right += len; } else { if(left != right) { string del = s.substr(left,len); ++target[del]; ++count; left += len; } else { right += len; left += len; } } if(count == 0) { ret.push_back(left); string del = s.substr(left,len); ++target[del]; ++count; left += len; } } } return ret; } }; 
三、总结
滑动窗口算法通过动态维护子区间的特性，在遍历的过程中高效地找到问题的解。它的核心思想是利用两个指针构建窗口，并根据问题的条件灵活调整窗口大小。相比暴力枚举，滑动窗口在优化时间复杂度方面有显著优势，非常适用于处理连续性问题，如子数组、子字符串及其变形的场景。
以上就是【优选算法篇·第二章：滑动窗口】的全部内容，欢迎指正~
码文不易，还请多多关注支持，这是我持续创作的最大动力！
