滑动窗口算法详解：从入门到实战

2. 无重复字符的最长子串 (LeetCode 3)

问题描述

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

解题思路

我们需要判断字符是否重复。由于 ASCII 字符集较小，可以用大小为 128 的数组模拟哈希表。

• right 进窗口时，对应字符计数 +1。
• 若某字符计数 > 1，说明重复，此时需移动 left 出窗口，直到重复字符被移除。
• 关键细节：left 移动过程中，对应的字符计数也要 -1，因为这些字符已不在窗口内。

代码实现

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) {
                // 移动 left 直到找到重复字符
                while(s[left] != s[right]) {
                    hash[s[left]]--; // 去掉标记
                    left++;
                }
                // 重复字符也出窗口
                hash[s[left]]--;
                left++;
            }
            len = max(len, right - left + 1); // 更新结果
            right++; // 继续进窗口
        }
        return len;
    }
};

3. 最大连续 1 的个数 III (LeetCode 1004)

问题描述

给定一个由若干 0 和 1 组成的数组 nums 以及一个整数 k，将数组中最多 k 个 0 翻转为 1，使得数组中连续 1 的个数最大化。

解题思路

这道题可以看作是在允许包含 k 个 0 的前提下，找最长的全 1 子数组。

• 维护一个变量 cnt 记录窗口内 0 的个数。
• right 右移，遇到 0 则 cnt++。
• 若 cnt > k，说明窗口非法，需要移动 left 出窗口，直到 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;
    }
};

4. 将 x 减到 0 的最小操作数 (LeetCode 1658)

问题描述

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

解题思路

直接思考从两边取数比较麻烦，不如换个角度：

• 设数组总和为 sum，我们要移除的元素之和为 x。
• 那么剩下的中间部分元素之和应为 sum - x。
• 问题转化为：在数组中找到和为 sum - x 的最长连续子数组。这样移除的次数（即总长度减去子数组长度）就是最小的。
• 同样利用正整数数组的单调性使用滑动窗口。

代码实现

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; // 记录子数组和与长度，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;
    }
};

以上四个例子涵盖了滑动窗口最常见的几种变形。核心在于理解如何定义'窗口'以及何时移动左右指针。掌握这些模式后，面对类似的子串/子数组问题，就能快速构建解决方案了。