滑动窗口算法常用于处理数组和字符串的子区间问题。通过四个 LeetCode 例题讲解其核心套路：维护左右指针，根据条件收缩或扩张窗口。涵盖最小长度子数组、无重复字符最长子串、最大连续 1 的个数及将 x 减到 0 的最小操作数。时间复杂度优化至 O(n)。
滑动窗口算法是笔试面试及算法竞赛中常见的算法，通常用于处理数组和字符串问题，尤其适合寻找满足特定条件的子数组或子字符串，以及连续子问题的计算。
滑动窗口的核心在于维护一个区间（窗口），其大小可以是固定的也可以是变化的。窗口在数据结构上移动来扫描数据。基本套路如下：
给定一个含有 n 个正整数的数组和一个正整数 target。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
提示：
1 <= target <= 10^91 <= nums.length <= 10^51 <= nums[i] <= 10^4本题是典型的滑动窗口应用。暴力解法时间复杂度为 O(n^2)，会超时。优化方案包括前缀和加二分查找 O(n log n)，或使用滑动窗口达到 O(n)。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size(), sum = 0, len = INT_MAX;
for (int left = 0, right = 0; right < n; right++) {
sum += nums[right]; // 进窗口
while (sum >= target) {
len = min(len, right - left + 1); // 判断
sum -= nums[left++]; // 出窗口
}
}
return len == INT_MAX ? 0 : len;
}
};
给定一个字符串 s，请你找出其中不含有重复字符的 最长 子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
提示：
0 <= s.length <= 5 * 10^4s 由英文字母、数字、符号和空格组成使用哈希表记录字符出现次数。移动右指针加入字符，若哈希值大于 1 说明有重复，则移动左指针出窗口直到满足条件。同时更新最大长度。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> hash;
int n = s.size();
int len = -1;
for (int i = 0, j = 0; j < n;) {
hash[s[j]] += 1;
while (hash[s[j]] > 1) {
hash[s[i++]]--;
}
len = max(len, j - i + 1);
j++;
}
return len == -1 ? 0 : len;
}
};
给定一个二进制数组 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。
提示：
1 <= nums.length <= 10^5nums[i] 不是 0 就是 10 <= k <= nums.length转化为求最长区间，区间内 0 的个数不超过 k。使用滑动窗口，统计窗口内 0 的数量，若超过 k 则移动左指针。
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int n = nums.size();
int cnt = 0;
int ret = -1;
for (int i = 0, j = 0; j < n; j++) {
if (nums[j] == 0) {
cnt++;
}
while (cnt > k) {
if (nums[i++] == 0) {
cnt--;
}
}
ret = max(ret, j - i + 1);
}
return ret == -1 ? 0 : ret;
}
};
给你一个整数数组 nums 和一个整数 x。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。
如果可以将 x 恰好 减到 0，返回 最小操作数；否则，返回 -1。
示例 1：
输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0。
提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^41 <= x <= 10^9将问题转化为求最长子数组，使其和等于 数组总和 - x。若目标值小于 0 直接返回 -1。使用滑动窗口寻找和为目标值的最大长度区间。
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int n = nums.size();
int k = 0;
for (auto s : nums) {
k += s;
}
k -= x;
if (k < 0) return -1;
int len = -1;
int sum = 0;
for (int i = 0, j = 0; j < n; j++) {
sum += nums[j]; // 进窗口
while (sum > k) {
sum -= nums[i++]; // 出窗口
}
if (sum == k) {
len = max(len, j - i + 1);
}
}
return len == -1 ? -1 : n - 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