前言：
目录
一、什么是滑动窗口？
下面我们通过一道例题来具体的看一下滑动窗口是什么：
理解完题意之后我们就来看一下下面的讲解：
二、滑动窗口的原理
三、滑动窗口的算法实现
-
简单滑动窗口：假设窗口大小为k，数据序列为S，滑动窗口算法如下：
-
动态窗口大小：当窗口大小动态变化时，需要根据实际情况调整算法。（上面图中我们举的例子就是一个动态滑动窗口）以下是一个简单的示例：
四、滑动窗口的例题讲解
4.1. 长度最小的子数组
这个就是上面的那个例题，算法原理我们已经讲过了，现在我们直接来看一下它的实现：
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size(), sum = 0, ret = INT_MAX;
for (int left = 0, right = 0; right < n; right++)
{
sum += nums[right]; //进窗口
while (sum >= target)
{
ret = min(ret, right - left + 1);
sum -= nums[left++]; //出窗口
}
}
return ret == INT_MAX ? 0 : ret;
}
通过这段代码我们可以看到滑动窗口一般分为这几步：
这几步就是滑动窗口类题的基本格式，大部分题直接套这个公式就行了，下面我们再来看几个题来巩固一下
4.2 无重复字符的最长子串
题意解析：本题要求的就是一个字符串中的不重复的最长字串，题意并不难理解，值得我们思考的有一点，就是当新元素进窗口时，我们如何可以知道它窗口中已经有这个元素呢？相信你心中已经有了答案，没错，就是借助哈希表来标记窗口中已经有过的字符，且当元素种类较少时，我们可以直接借助一个整形数组来模拟哈希表，下面我们先来看一下本题的推导过程，然后再看一下代码实现：
推导过程：
代码实现：
int lengthOfLongestSubstring(string s) {
int hash[128] = { 0 }; //使用数组来模拟哈希表
int left = 0, right = 0, n = s.size();
int ret = 0;
while (right < n)
{
hash[s[right]]++;
while (hash[s[right]] > 1)
{
hash[s[left++]]--; //出窗口
}
ret = max(ret, right - left + 1); //更新结果
right++; //让下一个元素进入窗口
}
return ret;
}
4.3 找到字符串中所有字母异位词
本题往简单点看就是找到字符串中的特定字串，只是并不要求顺序一致，这道题也是需要结合哈希表来实现的，跟上面的做题格式基本一致，下面我们直接来看一下代码实现：
vector<int> findAnagrams(string s, string p) {
vector<int> ret;
int hash1[26] = { 0 }; //统计字符串p中每个字符出现的个数
for (auto e : p) hash1[e - 'a']++;
int hash2[26] = { 0 }; //统计窗口里面每个字符出现的个数
int m = p.size();
for (int left = 0, right = 0, count = 0; right < s.size(); right++)
{
char in = s[right];
if (++hash2[in - 'a'] <= hash1[in - 'a']) count++; //进窗口+维护count
if (right - left + 1 > m)
{
char out = s[left++];
if (hash2[out - 'a']-- <= hash1[out - 'a']) count--; //出窗口+维护count
}
//更新结果
if (count == m) ret.push_back(left);
}
return ret;
}
感谢各位大佬观看，创作不易，还望各位大佬点赞支持！！！