滑动窗口算法核心思路与经典例题解析

无重复字符的最长子串

题目描述

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

实现核心及思路

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

1. 定义 left 和 right 指针，以及用于计数的数组 hash；
2. right 指针右移，标记字符出现次数；
3. 若发现重复（hash[s[right]] > 1），则移动 left 指针，直到重复字符被移出窗口；
4. 每次移动后更新最大长度。

关键点：left 右移出窗口时，必须同步减少 hash 表中对应字符的计数，确保窗口内的统计准确。

思路可视化

C++ 代码实现

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]]++; // 字符进窗口，计数 +1
            
            // 如果当前字符重复，收缩左边界直到不重复
            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;
    }
};

最大连续 1 的个数 III

题目描述

给定一个二进制数组 nums 和一个整数 k，允许翻转最多 k 个 0，求翻转后最长的连续 1 的个数。

实现核心及思路

此题可视为'允许窗口中包含最多 k 个 0'。我们只需维护窗口中 0 的个数 cnt，当 cnt <= k 时窗口合法。

1. 定义 left 和 right 指针，cnt 记录窗口内 0 的数量；
2. right 右移，遇到 0 则 cnt++；
3. 若 cnt > k，说明 0 太多了，需要移动 left 指针，直到 cnt 降回 k；
4. 在合法状态下，用窗口长度更新结果。

优化点：实际上不需要显式地让 cnt 回到 k 再更新结果，只要在 cnt > k 时更新一次即可，但为了逻辑清晰，我们在循环结束后再次检查一次边界情况。

C++ 代码实现

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0, right = 0;
        int size = nums.size();
        int result = 0, cnt = 0; // cnt 记录 0 的个数
        
        while(right < size) {
            if(nums[right] == 0) {
                cnt++; // 0 个数增加
                
                if(cnt > k) { // 0 超出限制，收缩左边界
                    result = max(result, right - left);
                    while(cnt > k) {
                        if(nums[left] == 0) {
                            cnt--; // 移除 0
                        }
                        left++;
                    }
                }
            }
            right++;
        }
        
        // 防止遍历完整个数组 cnt 仍小于等于 k 的情况
        result = max(result, right - left);
        return result;
    }
};

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

题目描述

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

实现核心即思路

直接思考从两端取数比较困难，不如转换视角：

假设我们从左边取了 sum1，右边取了 sum3，且 sum1 + sum3 = x。设数组总和为 sum，则中间剩余部分的和 sum2 = sum - x。

问题转化为：在数组中找到一个和为 sum - x 的最长连续子数组。这样，剩下的部分（即操作数）就是最少的。

由于所有元素大于 0，和具有单调性，可以直接使用滑动窗口。

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

C++ 代码实现

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