用滑动窗口做几道经典数组题

无重复字符的最长子串

题目描述

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

示例 1:

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

提示：

• 0 <= s.length <= 5 * 10^4
• s 由英文字母、数字、符号和空格组成

实现思路

这题窗口里要维护的是'没有重复字符'。右指针每次进来一个字符，如果它在窗口里已经出现过，就从左边开始挪，直到重复被清掉。

我更习惯把它理解成'窗口里始终保持合法状态'，而不是一边扩一边想太多。字符集不大时，用哈希表记次数就够了，逻辑也清楚。

实现代码

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]] += 1;
            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 的最大个数。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1，最长的子数组长度为 6。

提示：

• 1 <= nums.length <= 10^5
• nums[i] 不是 0 就是 1
• 0 <= k <= nums.length

实现思路

这题本质上是在找一个最长区间，要求区间内 0 的数量不能超过 k。窗口里只要统计 0 的个数就行，一旦超过限制，就把左边界往右挪，直到重新合法。

和上一题相比，这题更像是'限制型窗口'。判断条件很明确，写起来也干净。

实现代码

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。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0。

提示：

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^4
• 1 <= x <= 10^9

实现思路

这题直接从两端删，思路会很散。更稳的办法是反过来想：删掉的部分越少，保留下来的中间子数组越长。于是问题就变成了——找一个最长子数组，它的和等于 数组总和 - 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;
    }
};

小结

滑动窗口不是固定模板，但它有一个很稳定的前提：窗口状态能随着左右指针移动被增量维护。正因为这样，遇到'连续区间''最短/最长子数组''限制某种计数'的题时，先想窗口通常不会错。

真到做题时，关键不是背步骤，而是先判断能不能把题改写成'窗口合法/不合法'的形式。能改，基本就顺了；改不了，再考虑前缀和、二分或者别的办法。