滑动窗口算法专题：四道经典题目深度解析

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

题目描述

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

实现思路

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

• right 右移，对应字符计数加一。
• 若发现重复（计数 > 1），则移动 left 指针，直到移除重复字符为止。移动过程中需将对应字符计数减一。
• 每次窗口调整后，更新最大长度。

代码实现

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = {0};
        int left = 0, right = 0;
        int size = s.size();
        int max_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++;
            }
            
            max_len = max(max_len, right - left + 1); // 更新结果
            right++; // 继续进窗口
        }
        return max_len;
    }
};

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

题目描述

给定一个由若干 0 和 1 组成的数组 nums 以及一个整数 k，如果可以将最多 k 个 0 替换为 1，那么数组中连续 1 的最大长度是多少？

实现思路

这道题本质上是允许窗口内包含最多 k 个 0。我们只需维护窗口中 0 的个数 cnt。

• right 右移，遇到 0 则 cnt++。
• 若 cnt > k，说明 0 的数量超标，需要移动 left 指针，直到 cnt <= k。移动过程中若遇到 0，则 cnt--。
• 窗口始终合法，直接记录最大长度即可。注意处理遍历结束后可能存在的未更新情况。

代码实现

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 的个数超过限制，收缩窗口
            while(cnt > k) {
                if(nums[left] == 0) {
                    cnt--;
                }
                left++;
            }
            
            // 更新结果，此时窗口 [left, right] 是合法的
            result = max(result, right - left + 1);
            right++;
        }
        return result;
    }
};

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

题目描述

给你一个整数数组 nums 和一个整数 x。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意修改后的数组前缀和与后缀和。你需要修改数组以使其和等于 x，求最少操作次数。如果无法做到，返回 -1。

实现思路

直接找前缀和后缀比较麻烦，不如转换思路：

• 设数组总和为 sum，我们要移除的元素和为 x。
• 那么剩下的中间部分子数组的和应为 val = sum - x。
• 问题转化为：在数组中找到和为 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;
    }
};

总结

滑动窗口的关键在于识别问题的单调性和状态维护方式。无论是求和、计数还是哈希映射，核心都是保持窗口的合法性。在实际刷题中，多思考如何转化问题（如第 4 题的前缀和转化），往往能化繁为简。