算法每日双题精讲——滑动窗口（最大连续1的个数 III，将 x 减到 0 的最小操作数）

🌟快来参与讨论💬，点赞👍、收藏⭐、分享📤，共创活力社区。 🌟

别再犹豫了！快来订阅我们的算法每日双题精讲专栏，一起踏上算法学习的精彩之旅吧！💪

💯前言

💯滑动窗口的作用

🎉最大连续 1 的个数 III

📖题目描述

🧠解题思路

🙋这个解题思路是怎么来的呢？

💻代码实现（以 C++ 为例）

📊复杂度分析

🎉将 x 减到 0 的最小操作数

📖题目描述

🧠解题思路

🙋这个解题思路是怎么来的呢？

💻代码实现（以 C++ 为例）

📊复杂度分析

💯总结

💯前言

嘿，小伙伴们！在算法这个神奇的世界里，滑动窗口算法就像是一颗闪闪发光的🌟明星哦，它在解决数组和字符串相关的问题时可太厉害了！今天呢，咱们就一起来看看另外两道超经典的题目 ——“最大连续 1 的个数 III” 和 “将 x 减到 0 的最小操作数”，看看滑动窗口算法在这两道题里是怎么大显身手的🧐

当我们遇到要在给定的数据结构里找满足特定条件的子结构这类问题时，滑动窗口算法就像一把神奇的🔑钥匙，能帮我们轻松打开解题的大门哦！

💯滑动窗口的作用

滑动窗口算法可有趣啦！它用两个同向的指针来定义一个会动的 “窗口” 哦，这个窗口就像一个调皮的😜小精灵，在数组或者字符串里跑来跑去呢。通过不停地调整窗口的大小和位置，它能时刻知道窗口里面元素的情况，这样就能很快找到我们想要的子序列或者子串啦。这种方法可比那种傻傻地把所有可能的子结构都检查一遍的暴力枚举法强多啦，它能让算法的效率像火箭一样🚀飞起来呢！

滑动窗口是利用单调性，用 “同向双指针” 来实现优化的哦。简单来说呢，就是指针只向前走，不会后退哦。

👇操作步骤大概是这样滴：

先把left和right都设成0，
然后把元素放进窗口里，接着判断一下，如果满足条件就缩小窗口，如果不满足就扩大窗口，
最后别忘了更新结果哦。
就这样一直重复，直到把整个数据结构都遍历完。这样就能巧妙地避开那些没必要的计算啦，是不是很聪明呢？😎

🎉最大连续 1 的个数 III

📖题目描述

给你一个二进制数组nums和一个整数k哦，你可以把数组里最多k个0变成1，然后呢，你要找出数组里连续1最多能有多少个。

🧠解题思路

首先，我们把两个指针left和right都放在数组的开头，再设一个count用来记录窗口里0的个数，初始值是0，还有一个maxLength用来记录最大连续1的个数，初始值是0。🧐
然后呢，我们把right指针往右移，每移一次，如果遇到0，就把count加1。😜
要是count比k大了，这就说明窗口里0太多啦，超过了能变的数量。这时候呢，我们就把left指针往右移。要是left指向的是0，就把count减1。😏
每次移动指针之后，我们都要更新maxLength哦，它应该是当前窗口里连续1的个数（right - left + 1 - count）和之前maxLength里比较大的那个值。👍
就这样一直重复步骤 2 - 4，直到left指针走到数组的末尾。最后，我们就可以把maxLength返回啦。🎉

🙋这个解题思路是怎么来的呢？

我们首先最容易想到解法一：暴力求解

👇现在我们来分析以下数组：

让left=right=0

👆right指向的不是 0，就让right++，是0，就让countzero++

👆 此时countzero>k，我们计算len=right-left

👆然后我们让left走到让countzero恢复为k的位置

重复以上过程直到right=nums.size()

💻代码实现（以 C++ 为例）

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        // 用于记录满足条件的最长子数组长度，初始化为0
        int len = 0;
        // 滑动窗口的右指针，初始指向数组开头
        int right = 0;
        // 滑动窗口的左指针，初始指向数组开头
        int left = 0;
        // 用于统计当前滑动窗口内0的个数，初始化为0
        int countzero = 0;

        // 只要右指针没有超出数组范围，就持续进行窗口的移动和调整操作
        while (right < nums.size()) {
            // 如果当前右指针指向的元素是0，就将窗口内0的计数加1
            if (nums[right] == 0)
                countzero++;

            // 当窗口内0的个数超过了允许的k值时，需要调整窗口
            while (countzero > k) {
                // 先将左指针向右移动一位（这里left++先使用left的值然后再自增）
                // 如果移动后左指针指向的元素是0，就将窗口内0的计数减1
                // 因为这个0即将被移出窗口，所以要相应地更新计数
                if (nums[left++] == 0)
                    countzero--;
            }

            // 更新满足条件的最长子数组长度
            // 这里right - left + 1表示当前窗口的长度
            // 通过比较当前窗口长度和之前记录的len，取较大值更新len
            len = max(len, right - left + 1);

            // 将右指针向右移动一位，继续扩大窗口以探索后续元素
            right++;
        }

        // 返回找到的满足条件的最长子数组长度
        return len;
    }
};

📊复杂度分析

时间复杂度：是 $O(n)$ 哦，这里的n就是数组的长度啦。因为在最坏的情况下，right指针要把整个数组遍历一遍，left指针最多也会遍历一遍整个数组呢。😎
空间复杂度：是 $O(1)$ 哦，因为我们只需要几个额外的变量来存指针和一些数，这些只需要常数大小的空间呢。🧐

🎉将 x 减到 0 的最小操作数

📖题目描述

给你一个整数数组nums和一个整数x哦。你要在数组里选一个连续的子数组，让这个子数组里所有数的和等于x，然后找出满足这个条件的最小操作数（其实就是子数组的最小长度啦）。要是没有这样的子数组，就返回-1哦。

🧠解题思路

我们先把left和right指针都放在数组开头，再设一个sum用来记录窗口里数的总和，初始值是0，还有一个minOp用来记录最小操作数，初始值设成一个很大的值，比如INT_MAX。🧐
接着，我们把right指针往右移，每移一次，就把新的数加到sum里。😜
当sum大于等于x的时候，我们就试着把left指针往右移，同时更新sum。在这个过程中，如果sum正好等于x，我们就比较一下当前窗口的长度（right - left + 1）和minOp，要是当前长度更小，就把minOp更新一下。😏
就这样一直重复步骤 2 和 3，直到right指针走到数组末尾。最后呢，如果minOp还是刚开始设的值，就说明没找到合适的子数组，返回-1；要是minOp变了，就把它返回。🎉

🙋这个解题思路是怎么来的呢？

我们列出以下数组：

💻代码实现（以 C++ 为例）

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        // 获取数组nums的大小
        int n = nums.size();
        // 初始化滑动窗口的右指针、左指针以及用于累加数组元素总和的变量sum，初始值都设为0
        int right = 0, left = 0, sum = 0;

        // 遍历数组nums，将所有元素累加至sum中，得到数组元素的总和
        for (int a : nums) sum += a;

        // 计算目标值target，即数组所有元素之和减去给定的目标值x。
        // 其含义是，如果能在数组中找到一个子数组，其和等于target，
        // 那么通过删除该子数组两侧的元素，就能使剩余元素之和等于x。
        int target = sum - x;

        // 用于记录当前滑动窗口内元素的和，初始值设为0
        int tmp = 0;
        // 用于记录满足条件的子数组的最大长度（后续会根据此计算最少操作次数），
        // 初始值设为 -1，表示尚未找到满足条件的子数组
        int len = -1;

        // 如果计算出的目标值target小于0，说明无法通过删除元素使剩余元素之和等于x，直接返回 -1
        if (target < 0) return -1;

        // 开始滑动窗口操作，只要右指针right没有超出数组nums的范围，就持续循环
        while (right < n) {
            // 将当前右指针right指向的元素累加到tmp中，以更新当前窗口内元素的和
            tmp += nums[right];

            // 当tmp大于目标值target时，需要通过移动左指针left来缩小窗口，调整tmp的值
            while (tmp > target) {
                // 将左指针left指向的元素从tmp中减去，并将左指针left向右移动一位（先执行减法操作，再移动指针）
                tmp -= nums[left++];
            }

            // 如果经过上述调整后，tmp的值恰好等于目标值target，
            // 说明找到了一个满足条件的子数组，更新len为当前窗口长度（right - left + 1）和之前记录的len中的较大值
            if (tmp == target) len = max(len, right - left + 1);

            // 将右指针right向右移动一位，继续扩大窗口以探索后续元素
            right++;
        }

        // 如果len仍然为 -1，说明在整个数组中没有找到满足条件的子数组，即无法通过删除元素使剩余元素之和等于x，返回 -1
        if (len == -1) return -1;

        // 返回达到目标值x所需的最少操作次数，操作次数等于数组的总长度n减去满足条件的子数组的最大长度len
        return n - len;
    }
};