滑动窗口算法详解与实战案例

滑动窗口算法详解

滑动窗口是一种利用双指针维护动态区间的高效技巧。通过移动左右指针来扩大或缩小窗口，我们可以在一次遍历中完成计算，时间复杂度通常为 O(n)。

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

核心思路

一般步骤可以概括为：

1. 定义 left 和 right 指针，初始指向首元素；
2. right 向右移动（进窗口），模拟数据进入；
3. 当不满足条件时，left 向右移动（出窗口），移除数据；
4. 根据具体情况更新结果。

结束条件通常是 right 越界。下面我们通过几个经典题目来深入理解。

209. 长度最小的子数组

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

核心思路：由于数组元素均为正整数，求和具有单调性，可以直接套用模板。

1. 定义 left 和 right 指针，同时指向首元素；
2. right 指针向右移动，进窗口并累加 sum；当 sum ≥ target 时，更新结果；
3. left 指针向右移动，出窗口，同时让 sum 减去 nums[left]，直到 sum < target。

注意：在出窗口过程中，如果仍满足 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. 出现重复字符，left 指针向右移动，直到找到重复字符，然后继续让 right++。

注意：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

题目描述：给定一个由若干 0 和 1 组成的数组 nums 以及一个整数 k，若可以将最多 k 个 0 替换成 1，则返回仅包含 1 的最长连续子数组的长度。

核心思路：相比上面找最长无重复的子串，此题允许掺杂 k 个 0，所以我们要控制窗口中 0 的个数，始终维护一个合法有效的窗口。

1. 定义 left 和 right 指针，同时指向开头；定义 cnt 记录 0 的个数（用来维护窗口合法）；
2. right 指针向右移动，进窗口：
   • 如果 nums[right] 等于 1 则 right++，并更新结果；
   • 如果等于 0，则 cnt++：如果 cnt <= k，说明窗口合法，right++，并更新结果；如果 cnt > k，则要多余的 0 出窗口，即让 left++，直到找到 0，让 cnt--，使得 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 个数不满足 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;
    }
};

1658. 将 x 减到 0 的最小操作数

题目描述：给你一个整数数组 nums 和一个整数 x。每一次操作时，你应当移除数组最左边或最右边的元素，然后从 x 中减去该元素的值。请注意修改数组的前缀和后缀。如果可以将 x 恰好减到 0，返回最小操作数；否则，返回 -1。

核心思路：直接上手比较麻烦，因为我们完全不知道该从左边找还是右边找。我们可以对问题进行转化：假设从左边和右边找到了几个连续的元素，求和为 x，则此时 x 可以被减到 0。设数组所有元素之和为 sum，又有 sum1 + sum3 = x，则 sum2 = sum - x。

我们只要在中间找到一个连续的和为 sum - x 的最长的子数组，就能找到最少的次数了。又因为所有数组元素都大于 0，则求和满足单调性，所以就能用滑动窗口来解决。

1. 预处理：求数组所有元素之和 sum，目标值 val = sum - x；
2. left 和 right 指针维护窗口，add 记录窗口中元素之和，len 记录中间子数组长度；

细节：将 len 初始化为 -1，如果没找到满足的子数组，不会更新 len 的值，返回 -1。

3. right++，向右移动进窗口，add += nums[right]：
   • 当 add < val，right 继续向右移动，进窗口；
   • 当 add > val，由于单调性，left++，出窗口，add -= nums[left]，循环，直到 add <= val，即当窗口合法；
   • 当 add == val，更新 len，记录 len 的最大值。

结束条件：right 越界。

4. 返回结果，nums.size() - len。

代码实现：

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;
    }
};