滑动窗口算法核心思路与经典例题解析

无重复字符的最长子串

题目描述

给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。

解题思路

要判断字符是否重复，需要一个标记机制。ASCII 字符集共有 128 个字符，我们可以用一个大小为 128 的数组模拟哈希表。当一个字符进入窗口时，对应位置计数加一；若值大于 1，说明出现了重复。

1. 定义 left 和 right 指针，同时指向字符串开头；
2. right 指针向右移动，进窗口，哈希表对应位置元素 ++；
3. 一旦发现重复字符（hash[s[right]] > 1），left 指针开始向右移动，直到移除重复字符为止；
4. 在 left 移动过程中，记得将移出窗口的字符计数减一。

注意：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，求翻转后最长的连续 1 的个数。

解题思路

此题可以看作是在找最长子串的基础上，允许掺杂 k 个 0。我们需要控制窗口中 0 的个数，始终维护一个合法有效的窗口。

1. 定义 left 和 right 指针，cnt 记录窗口中 0 的个数；
2. right 指针向右移动，如果遇到 0，cnt 加一；
3. 如果 cnt <= k，窗口合法，继续扩展；
4. 如果 cnt > k，说明 0 的个数超标，需要移动 left 指针，直到 cnt 重新等于 k。

优化点：实际上，当 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;
        while(right < size) {
            if(nums[right] == 0) {
                cnt++; // 0 个数更新
                if(cnt > k) { // 0 个数不满足要求
                    result = max(result, right - left); // 更新结果
                    // 左边的元素出窗口，直到 0 的个数重新满足要求
                    while(cnt > k) {
                        if(nums[left] == 0) {
                            cnt--;
                        }
                        left++;
                    }
                }
            }
            right++;
        }
        result = max(result, right - left); // 遍历结束后再次更新
        return result;
    }
};

将 x 减到 0 的最小操作数

题目描述

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

解题思路

直接思考如何从两边凑出 x 比较困难，不如换个角度：如果我们移除了两端的元素和为 x，那么中间剩下的部分和就是 sum - x。为了让操作数最少，也就是让移除的元素最少，等价于让中间剩下的子数组最长。

因此问题转化为：在数组中找到一个和为 sum - x 的最长连续子数组。

由于所有元素都大于 0，求和具有单调性，可以使用滑动窗口解决。

1. 预处理：计算数组总和 sum，目标值 val = sum - x；
2. 若 val < 0，直接返回 -1；
3. 使用 left 和 right 指针维护窗口，add 记录窗口和，len 记录最长子数组长度；
4. right 向右移动进窗口，add += nums[right]；
5. 当 add > val 时，left 向右移动出窗口，add -= nums[left]，直到 add <= val；
6. 当 add == val 时，更新 len 的最大值。

细节处理：len 初始化为 -1，用于标识未找到满足条件的子数组。最终返回 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;
        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;
    }
};