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

无重复字符的最长子串

题目描述

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

示例：

输入：s = "abcabcbb"
输出：3
解释：因为无重复字符的最长子串是 "abc"，所以其长度为 3。

题目分析

题目要求找特征字串，适合用滑动窗口解决。约束条件在于窗口内不能有重复字符。这与之前的题目类似，只是判断条件变成了字符计数。

实现思路

使用哈希表记录字符出现的次数。移动右指针，将字符加入窗口并增加计数。如果发现当前字符计数大于 1，说明有重复，此时移动左指针直到窗口内无重复字符。每次移动后更新最大长度。

实现代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> hash;
        int n = s.size();
        int len = -1;
        for (int i = 0, j = 0; j < n;) {
            hash[s[j]]++; // 进窗口
            while (hash[s[j]] > 1) {
                hash[s[i++]]--; // 出窗口
            }
            len = max(len, j - i + 1);
            j++;
        }
        return len == -1 ? 0 : len;
    }
};

最大连续 1 的个数 III

题目描述

给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0，则返回执行操作后 数组中连续 1 的最大个数。

题目分析

换个思路理解，这个问题等价于求一个最长区间，使得区间内 0 的个数不超过 k 个。既然数字只有 0 和 1，这就变成了求某特征区间的问题，可以直接套用滑动窗口模板。

实现思路

定义两个指针指向最左端，设置计数器记录窗口内 0 的数量。循环中，若当前值为 0 则计数加一。如果 0 的数量超过 k，则将左指针右移并减少计数，直到满足条件。最后更新最终答案。

实现代码

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        int cnt = 0;
        int ret = -1;
        for (int i = 0, j = 0; j < n; j++) {
            if (nums[j] == 0) {
                cnt++;
            }
            while (cnt > k) {
                if (nums[i++] == 0) {
                    cnt--;
                }
            }
            ret = max(ret, j - i + 1);
        }
        return ret == -1 ? 0 : ret;
    }
};

将 x 减到 0 的最小操作数

题目描述

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

题目分析

这道题具有迷惑性。我们可以将其转化一下：其实它问的是求一个最长的区间，区间里面的值等于原来数组的和减去 x。这样我们就变成了求最长区间的和等于目标值，依然可以使用滑动窗口来实现。

实现思路

第一步计算数组总和减去 x 得到目标值，如果小于 0 直接返回 -1。定义两个指针指向最左端，进入循环后将右指针的值加入窗口。如果窗口和大于目标值，将左指针指向的值移出窗口。跳出循环后更新结果。最后返回数组长度减去找到的最长子数组长度。

实现代码

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int n = nums.size();
        int k = 0;
        for (auto s : nums) {
            k += s;
        }
        k -= x;
        if (k < 0) return -1;
        
        int len = -1;
        int sum = 0;
        for (int i = 0, j = 0; j < n; j++) {
            sum += nums[j]; // 进窗口
            while (sum > k) {
                sum -= nums[i++]; // 出窗口
            }
            if (sum == k) {
                len = max(len, j - i + 1);
            }
        }
        return len == -1 ? -1 : n - len;
    }
};