初识算法 · 滑动窗口(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)，毕竟没有多开空间。
感谢阅读！
原文地址：https://blog.csdn.net/2301_79697943/article/details/142796756
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！