解锁高效算法思维：滑动窗口法，让你轻松搞定复杂题！（2）

解锁高效算法思维：滑动窗口法，让你轻松搞定复杂题！（2）

前言：

在算法学习中，滑动窗口是一种常用且高效的技巧，尤其适用于处理数组、字符串等连续数据结构的问题。滑动窗口可以帮助我们在不遍历整个数据集的情况下找到局部最优解，从而提高代码的运行效率。许多经典的算法题都可以通过滑动窗口的思想进行优化解决，比如求子数组的最大和、找到字符串中的特定子串等。

本篇博客将深入浅出地讲解滑动窗口的题目。通过一系列习题的详细解析，我们将带你逐步掌握滑动窗口的核心思路，帮助你在算法面试和日常开发中灵活运用这一技巧。无论你是算法初学者还是希望提升算法能力的开发者，都可以从中获得收获。下面我们进入代码世界。

1.最大连续1的个数（3）

1.1.题目来源

本题同样来自于力扣，下面我给出本题的链接：https://leetcode.cn/problems/max-consecutive-ones-iii/

1.2.题目解读

本题也是很容易去理解的，它就是给了我们一个二进制数组（指数组里面的数都是0,1），我们最多有k次机会可以把0变成1，让我们寻找这个数组连续1的最长个数，至于为什么是最多改变k次而不是改变k次，因为有时候会出现k比0大的情况，此时我们取小的那个就好了，这个就是本题表达给我们的意思，这个题目如果理解不通的话，难度会很大，如果理解了，那么难度会直接变小，下面小编给出本题的思路讲解。

1.3.题目思路讲解

1.3.1.转换题目的信息

如果本题我们真是按照它给我们的信息，我们老老实实的去把数组中的0改变k次个1的话，这个题目解起来会很艰难，因为我们不知道怎么改变k次才可以做到这个题目的解答，所以我们可以转换思想，我们可以通过一个计数器来记录一个数组中出现0的次数，此时我们无须让0变成1，仅仅计数就好，直到这个数超过了给定我们的k次，此时我们就不能把0变成1了，此时我们就要让左边往右边缩一下，直到计数器小于等于k次即可，所以本题我们依然可以采取滑动窗口的解法，我就不讲暴力解法了。

1.3.2.滑动窗口解法

对于滑动窗口，此时我们需要设置好两个指针分别指向开头（left和right），此时我们还需要一个计数器，让变量zero记录就好了，此时我们开始遍历数组，让right一直往右边走，倘若此时right位置的数据为0，那么我们让zero++，之后我们就要进入判断部分，判断的条件自然是计数器大于k次，此时我们在出窗口之前，先判断left位置的数据是否为0，如果为0，那么让count–，再让left往右走进行出窗口操作即可，此时我们在判断完后，再进行更新数据即可，此时记录数组的长度，通过max函数判断出遍历时的最小值，这便是滑动窗口解法，只要我们把题目的信息转换了以后，难度就会直接降级，下面小编开始代码部分的讲解。

1.4.代码实操

首先，我们先做预备操作，即准备好两个指针，计数器，以及记录数组长度的变量，下面给出代码：

int left = 0,right = 0,zero = 0,ret = 0;
int n = nums.size();

之后，我们就要进入循环来进行滑动窗口的操作了，这个循环和之前题目的判断条件是一样的，只要right不越界就好，下面给出代码：

while(right < n)
{}

在循环体内，我们就要进入滑动窗口那几个步骤的操作了，首先是入窗口，此时我们先判断right位置的数据是否为0，如果为0，计数器加1，之后就要进入判断环节，由于此时left位置的数据可能不为0，所以需要循环判断此时的计数器，循环的条件自然是计数器大于k，之后我们在出窗口之前，通过if语句判断此时的left是否为0，如果为0，让计数器减去一就好了，然后进行出窗口操作，left往右边走即可，在判断完后，我们更新结果，通过max函数找到最长的连续一的个数，然后在让right往右走即可。下面给出代码：

if(nums[right] == 0)
    zero++;
while(zero > k)
{
    if(nums[left] == 0)
    zero--;
    left++;
}
ret = max(ret,right - left + 1);
right++;

之后我们直接返回结果即可，此时这个代码就写完了，下面小编给出完整代码：

1.5.完整代码

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

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

2.1.题目来源

本题同样来自于力扣，下面我放上链接：https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/

2.2.题目解读

本题是给定了我们一个数组，让我们每次相加的时候都是拿数组最右边或者最左边的元素相加，直到加起来等于x的时候，此时我们就知道了让x减到0的操作数，可能这么让x减到0的操作数有很多种，我们要找到其中最小的，这便是这个题目的解读，如果我们找到了一个好的思路，那么这个题目就会很简单，但当我们按部就班的做，这个题目的难度是很大的，下面小编讲述本题的思路解析。

2.3.题目思路解析

2.3.1.转换题目的信息

如果我们真就按照题目的思路进行作答，那么会很麻烦，因为我们需要在左右分别找到合适的值相加，有时候单纯的一遍就可以找到，虽然说起来很简单，但是当我们落实到代码，这个代码的书写难度会很大，所以小编针对于这个题，给各位讲述一个我们在高中的时候学过的一个思想：正难则反的思想，这个思想我记着在概率部分习题常常用到，意思就是当一个题目正常做很难的话，那么我们就可以尝试它反过来的计算结果，有的时候反着求比正着求要简单的多，就比如本题目，我们如果找两头的数据是很难的，所以我们可以尝试寻找中间那部分等于sum（数组总和）- x的数据，因为我们要找到把x减到0的最小操作数，所以我们就要寻找中间那个加来等于sum - x的最大数，让数组总和减去这个最大数即就是我们要找到的最小操作数，这就是本题目最重要的转换题目信息的操作，记住正难则反的思想，它可以帮助我们解决一些很难的问题。

2.3.2.滑动窗口解法

本题同样也是可以使用暴力解法求解的，我就不在单独说了，因为我相信知道了正难则反思想的你，一定会想到如何用暴力解法解决这个题目，这个题目，我们可以用滑动窗口更快的做出来，滑动窗口的题目做来做去还是那几步，首先我们需要定义两个指针，均指向开头，一个代表着左区间，一个代表着右区间，还需要一个计数器记录此时符合条件的区间长度，此时我们直接遍历数组，首先入窗口，让一个变量h记录此时区间数值的大小；然后进行判断，判断的条件肯定是此时的h大于了sum - x，如果大于了我们就开始出窗口，出完窗后，我们就要判断此时的h是否为sum - x，如果是的话，那么我们就更新结果，通过循环我们就可以找到把x变为0的操作数，最后的结果不要忘记用总数减去计数器，因为我们是反着求的，这便是本题的思路讲解，下面小编进入代码实操的部分。

2.4.代码实操

刚开始我们需要准备本题的变量，因为是滑动窗口，自然涉及了双指针，并且我们还需要计数器记录区间长度，sum记录数组的和，当然，我们需要关注细节问题，倘若此时没有最小操作数，那我们就返回-1，所以我们在定义计数器的时候就可以直接定为-1，下面给出这部分代码：

int left = 0,right = 0,ret = -1,sum = 0,h = 0,n = nums.size();  //ret应该为 - 1，因为它有0这种情况，当x为所有元素的和的时候，此时就是为0，操作数就是元素的个数

之后我们需要求一下数组所有元素的和，通过范围for求和即可：

//求出整个数组的和
    for(auto e : nums)
    {
        sum += e;
    }C

在我们进入滑动窗口之前，我们还需要注意一个细节问题，倘若此时给定我们的操作数要大于我们数组所有长度之和，那么此时就意味着不可能存在最小操作数，我们直接返回-1即可：

int target = sum - x;
//细节问题，此时可能x要大于sum
if(target < 0)
return - 1;

之后我们就可以循环进入滑动窗口，循环的条件还是和上面一样，只要right不超过数组长度即可：

while(right < n)
{}

在循环体内，我们首先要是入窗口操作，让h记录区间长度即可，之后我们进入判断部分，此时的判断我们还是需要循环判断，因为此时的数组在出完一次窗后h还有可能大于target，所以我们在这个循环判断体内，首先是把h里面的左窗口元素进行出窗，然后left往后走；结束完判断条件后，我们还需要判断此时的h是否等于target，如果等于我们就更新一次数据，用max()函数找出最大值，然后继续让right往后走即可，这便是循环体的内容：

 h += nums[right];
while(h > target)
{
    h -= nums[left];
    left++;
}
if(h == target)
ret = max(ret,right - left + 1);
right++;

最后我们在返回的时候用三目操作符判断一下此时的ret是否为-1，若还是-1，证明此时没有最大数，更不会有操作数，直接返回-1就好，反着返回最小操作数：

return ret != -1 ? n - ret : -1;

下面我给出完整代码。

2.5.代码展示

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int left = 0,right = 0,ret = -1,sum = 0,h = 0,n = nums.size();  //ret应该为 - 1，因为它有0这种情况，当x为所有元素的和的时候，此时就是为0，操作数就是元素的个数
        //求出整个数组的和
        for(auto e : nums)
        {
            sum += e;
        }
        int target = sum - x;
        //细节问题，此时可能x要大于sum
        if(target < 0)
        return - 1;
        while(right < n)
        {
            h += nums[right];
            while(h > target)
            {
                h -= nums[left];
                left++;
            }
            if(h == target)
            ret = max(ret,right - left + 1);
            right++;
        }
        return ret != -1 ? n - ret : -1;
    }
};

3.总结

今天的两道算法题到这也就结束了，这俩算法题都有一个共性，它都要求我们要有转换题目条件的思想，这是我们在今后做算法题的时候最需要去培养的，希望各位读者都可以做到这一点，如果文章有错误，评论区指出，我会定时回复各位，一起做题的时光总是很短暂，那么各位大佬们，我们下一篇文章见啦！