初识算法 · 滑动窗口(2)

前言：

本文的主题是滑动窗口，通过两道题目讲解，一道是最大连续1的个数，一道是将x减到0的最小操作数。

链接分别为：

1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

1004. 最大连续1的个数 III - 力扣（LeetCode）

题目分为三个部分讲解，一是题目解析，二是算法原理，三是算法编写，那么，话不多说，直接进行主题咯。

最大连续1的个数III

题目解析

我们拥有一个数组，数组里面的值非0即1，还给了我们一个整数k，代表我们可以翻转最多k个0，要求返回的值是连续1的最大个数。

那么根据示例呢，我们也清楚了，需要我们选定一个头，从头开始，遍历数组，途中找到零可以反转，只要不超过个数就可以，反转之后，判断该长度是否为最长的连续1数组，比如示例1，两个0加后面的4个1，刚好符合条件，所以我们返回的是6，这是我们需要做的。

那么照例，暴力解法我们放在该部分介绍。

有没有暴力解法呢？当然是有的，我们无非就是从数组下标为0的地方开始，一直往后走，有零看能不能反转，如果可以翻转就继续往下走，不可以就存储该长度，最后返回所有长度的最大值就可以了。

暴力解法的时间复杂度是标准的O(N^2)，这道题也是可以通过的，具体编写呢就给同学们啦。

基本题目我们已经清楚了，现在我们就进行算法原理部分。

算法原理

我们这道题目使用的是滑动窗口，那么为什么使用滑动窗口呢？或者说为什么我们根据题目解析一看就知道要使用滑动窗口呢？

因为该题目的基本要求是一个连续的数组，也就是需要一段连续的空间，所以我们基本上可以断定为使用滑动窗口。

好了，既然需要使用滑动窗口，我们的三部曲，进窗口，出窗口，更新结果。

进窗口肯定是需要right来进的，进的时候需要注意的肯定只有0了，所以我们需要一个zero计时器，如果进窗口的时候是0，那么countzero++，出窗口的前提就是判断，判断的条件自然是如果countzero > k，也就是翻转的0上限了，所以需要出数据了，出肯定是left++，当left等于0的时候，即碰到0，此时left++，并且countzero--，就可以成功出掉数据。

此时，更新结果，一套流程下来，就没有啦。

算法编写

class Solution
{
public:
    int longestOnes(vector<int>& nums, int k) 
    {
        int countzero = 0, ans = 0;
        for(int left = 0, right = 0; right < nums.size(); right++)
        {
            if(nums[right] == 0) countzero++; //进窗口
            while(countzero > k)//判断 + 出窗口
                if(nums[left++] == 0) countzero--;
            ans = max(ans,right - left + 1);
        }
        return ans;
    }
};

根据代码的编写，时间复杂度接近N的，但是肯定还是小于暴力解法的，空间复杂度是O(1)，毕竟没有额外的开空间。

将x减到0的最小操作数

题目解析

题目要求和往常的稍微有点不一样，移除的元素不是数组中间的元素，而是数组最左边或者数组最右边的元素，选择最左边或最右边的值，x减去该值，最后x等于0返回的是减去的最小操作值。

这题目一看好像和滑动窗口没有关联，但是，题目特殊点在于减去的是最左边或者最右边的值。

那么我们不妨，将题目改造成，求一段区间，该区间的值等于该数组的总和 - x。

那么暴力解法就很简单了，两个循环，确定一个起点，然后遍历，用一个变量存储值，然后比较即可。

时间复杂度也是标准的O(N^2)，优化就和之前一摸一样了，优化之后就是滑动窗口了。

算法原理

其实本题的算法原理在题目解析部分就已经介绍的七七八八了，无非就是一段区间，进窗口，变量++，判断变量是否大于target，大于就--，最后判断变量是否==0，如果等于0，更新结果就可以了，其实这道题还没有第一题难。

如果不逆向思维，那么这道题还是挺难做的。

算法编写

class Solution
{
public:
    int minOperations(vector<int>& nums, int x) 
    {
        int sum = 0;
        for(int a : nums) sum += a;
            int target = sum - x;
        // 细节问题
        if(target < 0) return -1;
        int ret = -1;
        for(int left = 0, right = 0, tmp = 0; right < nums.size(); right++)
        {
            tmp += nums[right]; // 进窗⼝
            while(tmp > target) // 判断
            tmp -= nums[left++]; // 出窗⼝
            if(tmp == target) // 更新结果
            ret = max(ret, right - left + 1);
        }
        if(ret == -1) return ret;
        else return nums.size() - ret;
        }
};

时间复杂度也是接近O(N)了。空间复杂度为O(1)，毕竟没有多开空间。

感谢阅读！