滑动窗口算法通过维护一个动态区间解决连续子数组或子串问题。核心思想是利用双指针 left 和 right 控制窗口范围，结合单调性减少无效枚举。涵盖多个经典案例，包括最小长度子数组、无重复字符最长子串、最大连续 1 的个数 III、将 x 减到 0 的最小操作数、水果成篮、字母异位词及最小覆盖子串。相比暴力解法，该算法通常能将时间复杂度优化至 O(N)，适用于需要统计连续区间性质的场景。代码实现主要使用 C++，包含哈希表辅助计数及数组模拟哈希等技巧。
classSolution {
public:
intminSubArrayLen(int target, vector<int>& nums){
int n = nums.size();
int len = INT_MAX;
sum = ;
( left = , right = ; right < n; right++) {
sum += nums[right];
(sum >= target) {
len = (len, right - left + );
sum -= nums[left++];
}
}
len == INT_MAX ? : len;
}
};
int
0
// 进窗口
for
int
0
0
// 插入数据
// 判断
while
// 更新
min
1
return
0
个人思考
到 sum >= target。没有必要继续 right++，而是改变 left 位置不断进行判断，这里在双指针算法篇章有所说明，用于规避没有必要的枚举行为。
滑动窗口的正确性：利用单调性，规避了很多没有必要的枚举行为。
虽然代码使用两层循环，但是时间复杂度优化为 O(N)，时间复杂度主要是看思想。这里就 left 和 right 滑动。N + N = 2N ~ N.
我们根据题目需求模拟实现流程，取一部分区间进行观察（pww）。从 p 出发向右枚举可能的情况，直到遇到 pw 时结束，然后将起点右移，而不是继续枚举。由于我们从全知视角进行观察，继续枚举 pww 不符合题目要求，因此选择停止。为了判断字符是否重复出现，我们使用哈希表。
解法二：滑动窗口
比起如何实现逻辑，更重要的是如何知道为什么需要使用滑动窗口思想，不然就是巧妇难为无米之炊。
从图中可以看到，right 指向元素 a，导致哈希表中下标为 a 的元素值为 2，出现了重复情况。此时需要移动 left 指针，重新计算子串长度，但 left 应该移动到哪里呢？
很明显，right 停下是因为遇到了重复字符。如果没有重复字符，right 就可以继续向右移动。因此，left 需要跳过重复字符，之后 right 才能继续向右扩展，重新计算长度。
问题在于，left 应该跳到什么位置？由于 right 停下是因为遇到重复字符，left 应该跳过重复字符，否则无论 left 移动到哪里，在 [left, right] 区间内，right 都不会再前进，因为该区间内仍然有重复字符。完成这一步后，right 不需要回到 left 位置，继续向右移动即可。
判断条件就是 hash 是否出现重复字符，如果出现重复需要不断移除字符次数和移动 left 位置，直到 left 达到重复字符的下一个位置。
代码实现
classSolution {
public:
intlengthOfLongestSubstring(string s){
int hash[128] = {0};
int n = s.length();
int ret = 0;
for (int left = 0, right = 0; right < n; right++) {
hash[s[right]]++;
while (hash[s[right]] > 1) hash[s[left++]]--;
ret = max(ret, right - left + 1);
}
return ret;
}
};
通过分析，'最多翻转 k 个零'的意思是对于数值为零的部分，我们最多可以翻转 [0, k] 个零，而目标是将所有零都翻转成一的状态。同时，我们需要返回连续 1 的最大个数，即找到最长的连续 1 子数组。从红色部分可以看到，当零的个数超过 k 时，翻转就会停止。这道题与上一道题非常相似，因此我们可以引入一个变量 count 来统计当前子数组中零的个数，以便满足题目的要求。
解法一：暴力枚举 + zero 计数器
如果使用暴力枚举法来处理所有情况，针对每个零进行翻转操作，最后还需要再将其翻转回去，这种做法既繁琐又容易出错。此时，我们应该思考，既然翻转不能超过 k 个零，是否真的需要执行复杂的翻转操作呢？
可以将问题转化为：寻找一个最长的子数组，其中零的个数不超过 k 个。
解法二：滑动窗口
当我们得到了暴力解法的逻辑，现在需要模拟实现发现规律，进行优化。
首先，当 right 指针停下时，left 需要移动到下一个 1 的位置，这样 right 就无法继续移动了。这种情况的发生是由于 count > 2，因此需要调整 left 指针的位置，直到 count <= 2 为止。通过这种方式，能够确保 right 继续向前推进，同时维护零的个数不超过 2。
其次，当 left 移动到合适的位置后，right 不需要重新回到 left 的位置重新移动，因为 [left, right] 已经是一个合法的区间。
代码实现
classSolution {
public:
intlongestOnes(vector<int>& nums, int k){
int n = nums.size();
int count = 0;
int 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(len, right - left + 1);
}
return len;
}
};
classSolution {
public:
intminOperations(vector<int>& nums, int x){
int len = nums.size();
int sum = 0;
for (int a : nums) sum += a;
int target = sum - x;
int ret = -1;
if (target < 0) return-1;
for (int left = 0, right = 0, tmp = 0; right < len; right++) {
tmp += nums[right];
// 进窗口while (tmp > target) {
tmp -= nums[left++];
}
if (target == tmp) ret = max(ret, right - left + 1);
}
if (ret == -1) return ret;
elsereturn len - ret;
}
};
classSolution {
public:
inttotalFruit(vector<int>& f){
int n = f.size();
int hash[100001] = {0};
int len = 0, kinds = 0;
for (int left = 0, right = 0; right < n; right++) {
if (hash[f[right]] == 0) kinds++;
hash[f[right]]++;
while (kinds > 2) {
hash[f[left]]--;
if (hash[f[left]] == 0) kinds--;
left++;
}
len = max(len, right - left + 1);
}
if (kinds == 1) return n;
elsereturn len;
}
};
在模拟过程中，right 指针会移动 len 的位置，因此我们需要判断条件为 right + len <= s.size()，以确保窗口不会超出字符串 s 的边界
代码实现
classSolution {
public:
vector<int> findSubstring(string s, vector<string>& words){
vector<int> v;
unordered_map<string, int> hash1;
for (auto& str : words) hash1[str]++;
int len = words[0].size(), m = words.size();
// 进行 len 次滑动窗口for (int i = 0; i < len; i++) {
unordered_map<string, int> hash2;
for (int left = i, right = i, count = 0; right + len <= s.size(); right += len) {
// 进窗口
string in = s.substr(right, len);
hash2[in]++;
if (hash1[in] && hash2[in] <= hash1[in]) count++;
if (right - left + 1 > len * m) {
// 出窗口
string out = s.substr(left, len);
if (hash1[out] && hash2[out]-- <= hash1[out]) count--;
left += len;
}
if (count == m) v.push_back(left);
}
}
return v;
}
};
classSolution {
public:
string minWindow(string s, string t){
int hash1[128] = {0};
int kind = 0;
for (auto& ch : t) {
if (hash1[ch]++ == 0) kind++;
}
int hash2[128] = {0};
int count = 0; // 种类int len = INT_MAX;
int begin = -1;
for (int left = 0, right = 0; right < s.size(); right++) {
char in = s[right];
hash2[in]++;
if (hash2[in] == hash1[in]) count++;
while (count == kind) {
// 更新结果if (right - left + 1 < len) {
len = right - left + 1;
begin = left;
}
char out = s[left++];
if (hash2[out] == hash1[out]) count--;
hash2[out]--;
}
}
if (begin == -1) return"";
elsereturn s.substr(begin, len);
}
};
