滑动窗口算法详解：LeetCode 经典例题实战

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

题目描述

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

解题思路

我们需要判断字符是否重复。ASCII 字符集较小，可以用大小为 128 的数组模拟哈希表。当字符进入窗口时计数加一，若值大于 1 则表示重复。

1. 定义 left 和 right 指针。
2. right 移动，对应字符计数加一。
3. 若发现重复（计数 > 1），则移动 left 直到重复字符被移出窗口，同时减少对应计数。
4. 每次窗口调整后更新最大长度。

注意：left 移动过程中，必须同步减少哈希表中对应位置的计数，因为这些字符已不在窗口内。

图解示意

代码参考

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = {0};
        int left = 0, right = 0;
        int 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;
    }
};

3. 最大连续 1 的个数 III

题目描述

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0，则返回数组中连续 1 的最大个数。

解题思路

这题本质上是找包含最多 k 个 0 的最长子数组。我们只需控制窗口中 0 的个数，始终维护一个合法有效的窗口。

1. 定义 cnt 记录窗口中 0 的个数。
2. right 移动，遇到 0 则 cnt++。
3. 若 cnt > k，说明 0 太多，需要移动 left 直到 cnt <= k。
4. 在 cnt > k 时更新结果，或者最后统一更新。

优化点：实际上当 cnt 超过 k 时，窗口长度即为 right - left（因为此时 right 刚进来，还没算入合法长度）。但为了逻辑清晰，可以在循环结束后再更新一次最大值，防止遍历完整个数组时 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++;
                if(cnt > k) {
                    result = max(result, right - left);
                    while(cnt > k) {
                        if(nums[left] == 0) cnt--;
                        left++;
                    }
                }
            }
            right++;
        }
        result = max(result, right - left);
        return result;
    }
};

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

题目描述

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

解题思路

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

假设我们从左边取了若干元素，右边取了若干元素，它们的和为 x。设数组总和为 sum，中间剩余部分的和为 sum2。则有： sum1 + sum3 = x (两边之和) sum1 + sum2 + sum3 = sum (总和) => sum2 = sum - x

转化问题：我们要找的是中间一段连续子数组，其和为 sum - x，且长度最长。这样剩下的两端元素最少，即操作数最少。

由于所有元素为正，求和具有单调性，依然可以使用滑动窗口。

1. 预处理求总和 sum，目标子数组和 val = sum - x。
2. 若 val < 0，直接返回 -1。
3. 使用滑动窗口寻找和为 val 的最长子数组，记录长度 len。
4. 最终结果为 nums.size() - len。

代码参考

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