滑动窗口算法核心思路与四道经典题解

题目二：无重复字符的最长子串

问题背景

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

解题思路

这道题的核心在于判断字符是否重复。我们需要一个数据结构来标记窗口内字符的出现次数。由于 ASCII 字符集较小，可以用大小为 128 的数组模拟哈希表。

1. 初始化：hash 数组全 0，left 和 right 指针归零。
2. 扩展窗口：right 右移，对应字符计数加 1。
3. 处理重复：如果某字符计数大于 1，说明出现重复。此时需要移动 left 指针，同时减少对应字符的计数，直到重复字符被移出窗口。
4. 更新结果：每次有效移动后，计算当前窗口长度并更新最大值。

细节提示：在 left 移动过程中，必须同步减少 hash 数组中的计数，因为这些字符已经不在窗口中了。当遇到重复字符时，不仅要跳过它，还要将其从计数中移除，以便后续再次进入窗口。

代码实现

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = {0};
        int left = 0, right = 0;
        int size = s.size();
        int 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 的最长连续子数组的长度。

解题思路

相比上一题，此题允许窗口内存在一定数量的'非法'元素（即 0）。我们需要控制窗口中 0 的个数，始终维护一个合法有效的窗口。

1. 初始化：cnt 记录窗口中 0 的个数。
2. 扩展窗口：right 右移。如果是 1，直接更新结果；如果是 0，cnt 加 1。
3. 约束检查：当 cnt > k 时，说明 0 太多了，必须收缩窗口。移动 left 直到 cnt 重新小于等于 k。
4. 结果更新：在窗口合法的任何时刻，都可以更新最大长度。

优化思考：其实不需要严格维持 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 个数不满足 k，需要收缩
                    // 左边的元素出窗口，直到 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。如果不能将 x 减到 0，返回 -1。

解题思路

直接模拟从两边取数比较麻烦，因为不知道该从左还是从右开始。我们可以换个角度思考：

假设从左边取了 sum1，右边取了 sum3，且 sum1 + sum3 = x。设数组总和为 sum，则中间剩余部分的和 sum2 = sum - x。

转化目标：我们要找的是中间连续子数组的最大长度，使其和为 sum - x。这样剩下的两端元素之和就是 x，且操作次数最少（因为中间最长意味着两端最短）。

1. 预处理：计算数组总和 sum，目标值 val = sum - x。
2. 特殊情况：如果 val < 0，说明总和都不够，直接返回 -1。
3. 滑动窗口：在数组中寻找和为 val 的最长子数组。
   • add 记录当前窗口和，len 记录最大长度。
   • 若 add > val，收缩左边界。
   • 若 add == val，更新 len。
4. 返回结果：总长度减去中间最长子数组长度。

代码实现

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

通过以上四道题，我们可以看到滑动窗口算法在不同场景下的变体：从简单的单调求和，到带状态的哈希去重，再到约束计数和前缀和转化。掌握这些模式，能帮助你快速解决一类线性扫描问题。