滑动窗口算法详解与经典例题实战

滑动窗口核心思想

滑动窗口算法的核心在于用两个指针维护一个动态的区间。通过移动左右指针来扩大或缩小窗口，通常在一次遍历中就能完成计算，时间复杂度往往能优化到 O(n)。

典型应用场景：寻找最长无重复字符子串、找到和为目标值的最短子数组、字符串排列匹配等。

通用模板思路：

1. 定义 left 和 right 指针，初始都指向起始位置；
2. right 向右移动进窗口，更新状态；
3. 当窗口不满足条件时，left 向右移动出窗口，直到重新满足；
4. 在合法状态下更新结果。

结束条件通常是 right 指针越界。理解了这个框架，我们来看几个具体的例子。

案例一：长度最小的子数组

问题描述

给定一个含有 n 个正整数的数组和一个正整数 target，找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

解题思路

由于数组元素均为正整数，累加和具有单调性，这非常适合套用滑动窗口模板。

1. 初始化 left 和 right 指针，同时指向首元素；
2. right 指针向右移动，将元素加入窗口并累加 sum；
3. 当 sum >= target 时，说明当前窗口满足条件，尝试收缩左边界以寻找更短的子数组：left 右移，sum 减去 nums[left]，直到 sum < target；
4. 每次收缩前都要记录当前窗口的最小长度。

注意：在收缩窗口（left 移动）的过程中，只要依然满足 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，说明出现了重复。

1. 定义 left 和 right 指针，同时指向字符串开头；
2. right 向右移动，哈希表对应位置元素 ++；
3. 一旦发现重复（hash[s[right]] > 1），left 开始右移，直到移除重复字符为止。移出过程中，对应哈希值要 --；
4. 窗口合法时更新最大长度。

细节：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;
    }
};

案例三：最大连续 1 的个数 III

问题描述

给定一个二进制数组 nums 和一个整数 k，允许翻转最多 k 个 0，求翻转后数组中连续 1 的最大个数。

解题思路

这道题本质上是允许窗口中包含最多 k 个 0。相比上一个案例，这里不需要去重，而是控制特定元素的数量。

1. 定义 left 和 right 指针，cnt 记录窗口中 0 的个数；
2. right 向右移动，如果是 0 则 cnt++；
3. 如果 cnt <= k，窗口合法，直接更新结果；
4. 如果 cnt > k，说明 0 太多了，需要 left 右移，直到 cnt 降回 k。

优化技巧：其实最长子串出现在窗口中 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 个数不满足要求
                    result = max(result, right - left); // 更新结果
                    while(cnt > k) {
                        if(nums[left] == 0) {
                            cnt--; // 0 个数--
                        }
                        left++;
                    }
                }
            }
            right++;
        }
        result = max(result, right - left); // 再次更新结果
        return result;
    }
};

案例四：将 x 减到 0 的最小操作数

问题描述

给你一个整数数组 nums 和一个整数 x。每一次操作时，你应当移除数组最左边或最右边的元素，并从 x 中减去该元素的值。如果可以将 x 恰好减到 0，返回最小操作数；否则返回 -1。

解题思路

直接思考从两边取数比较麻烦，不如换个角度：如果我们从两端取走了若干元素，它们的和为 x，那么中间剩下的部分和就是 sum - x。为了让操作数最少，也就是让取走的元素最少，等价于让中间剩下的子数组最长。

因此，问题转化为：在数组中找到一个最长的连续子数组，使其和等于 sum - x。因为所有元素都是正数，求和具有单调性，可以直接用滑动窗口解决。

1. 预处理：计算数组总和 sum，目标值 val = sum - x；
2. 若 val < 0，直接返回 -1；
3. 使用滑动窗口寻找和为 val 的最长子数组，记录长度 len；
4. 最终结果为 nums.size() - len。

细节处理：len 初始化为 -1，如果没找到满足条件的子数组，len 保持 -1，此时应返回 -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;
        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;
    }
};

以上四个题目涵盖了滑动窗口在不同场景下的变体。掌握这些核心逻辑，遇到类似的双指针问题就能快速找到切入点。