滑动窗口算法实战：从入门到经典题型解析

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

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

思路解析： 这次我们需要判断字符是否重复。ASCII 码共有 127 个字符，我们可以用一个大小为 128 的数组模拟哈希表。当一个字符进入窗口时，对应位置计数加一；若计数大于 1，说明出现了重复。

1. 定义 left 和 right 指针，同时指向字符串开头。
2. right 指针向右移动，标记字符出现次数。如果某字符计数超过 1，说明窗口内有了重复。
3. 一旦检测到重复，left 指针开始向右移动，直到遇到那个重复字符为止。在此过程中，需要不断将移出窗口的字符计数减一。

注意：left 移动的过程中，必须同步更新哈希表状态，因为这些字符已经不在当前窗口中了。

代码实现：

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) { // 发现重复
                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 的个数 cnt，始终维护一个合法的窗口即可。

1. 定义 left 和 right 指针，cnt 记录窗口中 0 的个数。
2. right 指针向右移动，如果是 0 则 cnt++。
3. 如果 cnt <= k，窗口合法，直接更新结果；如果 cnt > k，说明 0 太多了，需要移动 left 指针出窗口，直到 cnt 重新等于 k。

优化点：其实最长子串往往出现在窗口中 0 的个数达到 k+1 的那一刻，所以可以在 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++;
                if(cnt > k) { // 0 个数超标
                    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 - x。为了让操作数最少，也就是让取出的元素最少，等价于让中间剩下的子数组最长。

因此，问题转化为：在数组中找到一个最长的连续子数组，使其和等于 sum - x。这又回到了经典的滑动窗口求和问题。

1. 预处理：计算数组总和 sum，目标值 val = sum - x。
2. 如果 val < 0，说明即使全取也不够，直接返回 -1。
3. 使用滑动窗口寻找和为 val 的最长子数组。right 进窗口累加 add，当 add > val 时 left 出窗口。
4. 当 add == val 时，记录当前窗口长度。
5. 最终结果为总长度减去找到的最长子数组长度。

注意：len 初始化为 -1，用于标记是否找到了满足条件的子数组。

代码实现：

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