滑动窗口算法的深入剖析
在算法学习的起始篇章里，我们已然接触到了双指针算法。借助之前几道算法题的讲解，相信你已能灵活驾驭双指针的运用。接下来，我们要深入探索另一个关键算法——滑动窗口。或许你会疑惑为何此前对该算法毫无耳闻，没关系，本篇将一步步为你阐释滑动窗口的原理以及适用场景，并通过几道算法题的剖析助力你深化理解。让我们开启本次的学习征程！
滑动窗口算法的深度探究" />
1.滑动窗口算法概述
实际上，滑动窗口算法属于双指针的一种特殊情形。之所以将其单独列为一种算法，是因为这种双指针具备特定的运行规律。那么，滑动窗口算法究竟是在何种双指针情境下产生的呢？我们来一探究竟。
在双指针的运用过程中，若两个指针从起始位置开始始终朝着同一个方向移动，且不存在反向移动的情况，这便属于滑动窗口。称其为滑动窗口，是因为两个指针同向移动时，恰似一个大小可变的窗口在数据中滑动。
滑动窗口算法的深度探究" />
明晰了滑动窗口的基本概念后，你或许会对其具体应用方式以及逻辑的合理性产生好奇。接下来，我们通过一道算法题来解开疑惑。
209. 长度最小的子数组（LeetCode）
依据题目描述，我们需要从给定数组中找寻和大于目标值target的最短子数组，并且该子数组必须是连续的区间。例如在示例1中，不能选取不连续的元素。
要是采用暴力枚举法，我们会设置指针left来遍历数组，指针right从left所在位置开始后移，统计left到right区间内的元素和，判断是否满足条件并记录子数组的长度。然而，暴力枚举的时间复杂度为O(N²)，在数据规模较大时容易超时。
于是我们思索优化办法。在暴力枚举的过程中，存在大量的重复计算。当right移动到使得left到right区间和大于等于target时，无需将right回退到left的位置，而是直接移动left并更新元素和，这样就规避了重复操作，这便是滑动窗口的优化思路，也验证了其合理性。
滑动窗口的操作步骤大致如下：
- 定义相关变量，例如子数组的长度、元素和等。
- 通过双指针遍历数组，依据条件调整指针的位置并更新结果。
以下是实现代码：
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums)
{
int n = nums.size(), len = INT_MAX, sum = 0;
for (int left = 0, right = 0; right < n; right++)
{
sum += nums[right];
while (sum >= target)
{
len = min(right - left + 1, len);
sum -= nums[left++];
}
}
return len == INT_MAX ? 0 : len;
}
};
2.滑动窗口相关算法题
2.1 无重复字符的最长子串（LeetCode 3）
题目要求从字符串中找出不含重复字符的最长子串。
暴力枚举法的时间复杂度较高，可通过滑动窗口进行优化。设置双指针，利用哈希表来判断窗口内是否存在重复字符，通过调整指针的位置来减少重复计算。
代码实现：
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
int hash[128] = {0};
int n = s.size(), len = 0;
for (int left = 0, right = 0; right < n; right++)
{
char in = s[right];
hash[in]++;
while (hash[in] > 1)
{
char out = s[left];
hash[out]--;
left++;
}
len = max(len, right - left + 1);
}
return len;
}
};
2.2 最大连续 1 的个数 III（LeetCode 1004）
题目要求将数组中最多k个0翻转，使得连续1的子数组长度最长。
我们将问题转化为求最长连续区间内0的个数不超过k，运用滑动窗口来解决。通过双指针和计数器来统计窗口内0的个数，调整指针的位置以更新最长长度。
代码实现：
class Solution
{
public:
int longestOnes(vector<int>& nums, int k)
{
int n = nums.size(), count = 0, len = 0;
for (int left = 0, right = 0; right < n; right++)
{
if (nums[right] == 0) count++;
while (count > k)
{
if (nums[left++] == 0) count--;
}
len = max(right - left + 1, len);
}
return len;
}
};
2.3 将 x 减到 0 的最小操作数（LeetCode 1658）
题目要求从数组两边选取元素，使得x减到0的操作数最少，我们将其转化为求数组中和为特定值的最长子数组。
通过滑动窗口来求解，统计数组的总和，将问题进行转化后，使用双指针和计数器来寻找最长子数组。
代码实现：
class Solution {
public:
int minOperations(vector<int>& nums, int x)
{
int sum = 0, s = 0, len = -1, n = nums.size();
for (auto i : nums) s += i;
sum = s - x;
if (sum < 0) return -1;
for (int count = 0, left = 0, right = 0; right < n; right++)
{
count += nums[right];
while (count > sum) count -= nums[left++];
if (count == sum) len = max(right - left + 1, len);
}
return len == -1 ? -1 : n - len;
}
};
2.4 水果成篮（LeetCode 904）
题目要求找出数组中最多包含两种水果的最长子数组。
运用滑动窗口，通过哈希表来统计窗口内水果的类型，调整指针的位置以确保窗口内的水果类型不超过两种，进而更新最长长度。
代码实现（数组模拟哈希表版）：
class Solution {
public:
int totalFruit(vector<int>& fruits)
{
const int N = 1e5 + 5;
int hash[N] = {0};
int n = fruits.size(), len = -1;
for (int left = 0, right = 0, kind = 0; right < n; right++)
{
int in = fruits[right];
if (hash[in]++ == 0) kind++;
while (kind > 2)
{
int out = fruits[left];
if (--hash[out] == 0) kind--;
left++;
}
len = max(len, right - left + 1);
}
return len;
}
};
2.5 找到字符串中所有字母异位词（LeetCode 438）
题目要求找出字符串s中p的所有异位词的起始索引。
通过滑动窗口，利用哈希表来统计字符出现的次数，调整指针的位置来判断窗口是否为异位词。
代码实现：
class Solution {
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> ret;
int hash1[26] = {0}, hash2[26] = {0};
int len = p.size();
for (auto& x : p) hash1[x - 'a']++;
int n = s.size();
for (int left = 0, right = 0, sum = 0; right < n; right++)
{
int in = s[right] - 'a';
hash2[in]++;
if (hash2[in] <= hash1[in]) sum++;
if (right - left + 1 > len)
{
int out = s[left] - 'a';
if (hash2[out] <= hash1[out]) sum--;
hash2[out]--;
left++;
}
if (sum == len) ret.push_back(left);
}
return ret;
}
};
2.6 串联所有单词的子串（LeetCode 30）
题目要求找出字符串中由所有单词串联形成的子串。
使用滑动窗口，考虑不同的起始位置，通过哈希表来统计单词出现的次数，调整指针的位置来判断是否为目标子串。
代码实现：
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words)
{
vector<int> ret;
unordered_map<string, int> hash1;
for (auto& x : words) hash1[x]++;
int gap = words[0].size();
int len = s.size(), count1 = words.size();
for (int i = 0; i < gap; i++)
{
unordered_map<string, int> hash2;
int count2 = 0;
for (int left = i, right = i; right < len; right += gap)
{
string tmp = s.substr(right, gap);
++hash2[tmp];
if (hash1.count(tmp) && hash2[tmp] <= hash1[tmp]) count2++;
while ((right - left + gap) / gap > count1)
{
string tmp = s.substr(left, gap);
if (hash1.count(tmp) && hash2[tmp] <= hash1[tmp]) count2--;
--hash2[tmp];
left += gap;
}
if (count1 == count2) ret.push_back(left);
}
}
return ret;
}
};
2.7 最小覆盖子串（LeetCode 76）
题目要求找出字符串s中覆盖字符串t的最小子串。
使用滑动窗口，通过哈希表来统计字符出现的次数，调整指针的位置来找到最小覆盖子串。
代码实现：
class Solution {
public:
string minWindow(string s, string t) {
int hash1[128] = {0}, hash2[128] = {0};
int count1 = 0;
for (auto& x : t)
{
if (hash1[x] == 0) count1++;
hash1[x]++;
}
int minlen = INT_MAX, begin = -1;
int n = s.size(), count2 = 0;
for (int right = 0, left = 0; right < n; right++)
{
char in = s[right];
hash2[in]++;
if (hash2[in] == hash1[in]) count2++;
while (count1 == count2)
{
if (right - left + 1 < minlen)
{
begin = left;
minlen = right - left + 1;
}
char out = s[left++];
if (hash1[out] == hash2[out]) count2--;
hash2[out]--;
}
}
if (begin == -1) return "";
else return s.substr(begin, minlen);
}
};
以上便是滑动窗口相关算法的详细讲解，后续还将带来更多算法内容，敬请期待！
相关文章
