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

2. 无重复字符的最长子串

题目描述

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

实现思路

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

• 进窗口：right 右移，对应字符计数 +1。
• 去重：如果某字符计数大于 1，说明重复。此时需要移动 left 指针，将重复字符之前的所有字符移出窗口（计数减 1），直到遇到重复的那个字符本身并将其移出。
• 更新：每次确保窗口内无重复后，更新最大长度。

细节：在 left 右移的过程中，必须同步减少哈希表中对应字符的计数，因为这些字符已经不在窗口范围内了。

代码实现

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

3. 最大连续 1 的个数 III

题目描述

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

实现思路

这道题可以看作是在允许存在 k 个 0 的情况下，寻找最长的全 1 子数组。核心在于维护窗口中 0 的个数不超过 k。

• 统计 0：定义 cnt 记录窗口内 0 的数量。
• 扩展：right 右移，遇到 0 则 cnt++。
• 收缩：如果 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 的个数增加
            }
            
            // 如果 0 的个数超过 k，收缩窗口
            if (cnt > k) {
                if (nums[left] == 0) {
                    cnt--; // 移除左侧的 0
                }
                left++;
            }
            
            // 更新最大长度
            result = max(result, right - left + 1);
            right++;
        }
        return result;
    }
};

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

题目描述

给你一个整数数组 nums 和一个整数 x。每一次操作时，你应当移除数组最左边或最右边的元素，并从 x 中减去该元素的值。你需要修改数组以供接下来的操作使用，并使得经上述操作后 x 恰好等于 0。返回所需的最小操作数；如果无法做到，返回 -1。

实现思路

直接思考从两端取数比较困难，我们可以转换视角：

设数组总和为 sum，我们要从两端取出的元素之和为 x。那么剩下的中间部分元素之和必然是 sum - x。 问题转化为：在数组中找到一个最长的连续子数组，使其和等于 sum - x。这样剩下的两端元素就是被移除的部分，且操作次数最少。

• 预处理：计算总和 sum，目标值 val = sum - x。
• 特殊情况：如果 val < 0，说明即使全部加起来也不够减，直接返回 -1。
• 滑动窗口：寻找和为 val 的最长子数组。由于元素均为正数，依然可以使用滑动窗口。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for (auto e : nums) sum += e;
        
        int val = sum - x;
        if (val < 0) return -1;
        
        int left = 0, right = 0;
        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;
    }
};

通过以上四个例子可以看出，滑动窗口的关键在于根据题目特性调整'进窗口'和'出窗口'的条件。掌握这些变体，基本能覆盖大部分线性扫描类算法题。