滑动窗口算法通过双指针维护动态区间，单次遍历解决子数组或子串问题。本文涵盖长度最小子数组、无重复字符最长子串、最大连续 1 的个数 III 及将 x 减到 0 的最小操作数四个经典案例，提供 C++ 代码实现与思路分析。
滑动窗口使用两个指针维护一个动态的'窗口'区间，通过移动指针来扩大或缩小窗口，在一次遍历中完成计算，时间复杂度通常为 O(n)。
典型应用：寻找最长无重复字符的子串、找到和为目标值的最短子数组、字符串的排列匹配。
一般步骤（模板）：
结束条件：当 right 越界。
给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0。
由于数组元素均为正整数，求和时满足单调性，套用滑动窗口模板：
注意：在出窗口时，如果满足 sum >= target，也要更新结果。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int left = 0, right = 0;
int len = INT_MAX, sum = 0;
while(right < nums.size()) {
sum += nums[right]; // 求和
while(sum >= target) { // 保证窗口合法
len = min(len, right - left + 1); // 更新结果
sum -= nums[left++]; // 出窗口
}
right++; // 继续进窗口
}
return len == INT_MAX ? 0 : len;
}
};
给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
找不含重复字符的最长子串，需要一个标记来判断字符是否重复。ASCII 总共有 127 个字符，用一个大小为 128 的数组模拟哈希表，当一个字符进窗口就数组中与其映射位置上的元素++，只要值大于 1 就说明重复。
注意：left 向右移动过程中（出窗口），哈希表对应位置的元素要--，因为这些字符已经不在窗口中了。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int hash[128] = {0};
int left = 0, right = 0, size = s.size(), len = 0;
while(right < size) {
hash[s[right]]++; // 标记
// 重复
if(hash[s[right]] > 1) {
// 找重复字符，保证窗口合法（出窗口）
while(s[left] != s[right]) {
hash[s[left]]--; // 去掉标记
left++;
}
// 重复字符出窗口
hash[s[left]]--;
left++;
}
len = max(len, right - left + 1); // 更新结果
right++; // 继续进窗口
}
return len;
}
};
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0，则返回数组中连续 1 的最大个数。
相比上面找最长无重复的子串，此题就是在此基础上可以掺杂 k 个 0，所以我们要控制窗口中 0 的个数，始终维护一个合法有效的窗口。
优化：最长子串其实在窗口中的 0 的个数等于 k + 1 时，所以，我们只需要在 cnt > k 时更新结果。但这样做，还需要在最后再更新一下结果，防止遍历完整个数组 cnt 还是小于等于 k。
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left = 0, right = 0; // 左右指针，维护窗口
int size = nums.size();
int result = 0, cnt = 0; // 记录结果和当前遍历到的 0 的个数
while(right < size) {
if(nums[right] == 0) {
cnt++; // 0 个数更新
if(cnt > k) { // 0 个数不满足 k
result = max(result, right - left); // 更新结果
// 左边的元素出窗口，直到 0 的个数重新满足要求
while(cnt > k) {
if(nums[left] == 0) {
cnt--; // 0 个数--
}
left++;
}
}
}
right++;
}
result = max(result, right - left); // 再次更新结果
return result;
}
};
给你一个整数数组 nums 和一个整数 x。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意修改数组的前缀和后缀。如果可以将 x 恰好减到 0，返回最小操作数；否则，返回 -1。
直接上手非常麻烦，因为完全不知道该从左边找还是右边找。对问题进行转化：假设从左边和右边找到了几个连续的元素，求和为 x，则此时 x 可以被减到 0。设数组所有元素之和为 sum，又有 sum1 + sum3 = x，则 sum2 = sum - x。
只要在中间找到一个连续的和为 sum - x 的最长的子数组，就能找到最少的次数了。又因为所有数组元素都大于 0，则求和满足单调性，所以就能用滑动窗口来解决了。
细节：将 len 初始化为 -1，如果没找到满足的子数组，不会更新 len 的值，返回 -1。
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
// 预处理：求和
int sum = 0;
for(auto e:nums) sum += e;
int left = 0, right = 0; // 左右窗口
// 转化为中间找一个和为 sum - x 的子数组
int val = sum - x;
// 处理特殊情况
if(val < 0) return -1;
int add = 0, len = -1; // 记录子数组和与长度
while(right < nums.size()) {
add += nums[right++]; // 进窗口
while(add > val) {
add -= nums[left++]; // 出窗口
}
if(add == val) {
len = max(len, right - left); // 更新结果
}
}
if(len == -1) return -1;
else return nums.size() - len;
}
};
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online