【滑动窗口】最大连续1的个数|将x减到0的最小操作数

---

`

---

1.最大连续1的个数

解法：

• 1.暴力解法
• 给定一个left指针固定左端点元素，再给定一个right指针从左端点元素开始遍历。
• • 当遇到1时，让一个计数器cnt+1，当遇到0时，让统计0的计数器sum+1，同时总的计数器也+1。当统计0的计数器sum>=k时，说明0翻转的次数用完了。所以统计当前的最长长度（1和0）。
• 随后进行下一次循环，left往后走一格，right从left位置开始往后走，同时清空总长度计数器和统计0的计数器重新开始遍历，重复上述操作即可。

时间复杂度O(n^2)

• 2.滑动窗口
• 在暴力解法的基础上，当统计0的计数器sum>k时，不再回到left位置重新开始遍历。而是让left位置的元素出窗口，同时继续判断当前的统计0的计数器是否还是>k，因为left位置出的元素可能是0。这样，在保证翻转的0的个数<=k的前提下，遍历一边数组就能找到最长的长度。

时间复杂度O(n)

滑动窗口代码：

class Solution {
public:int longestOnes(vector<int>& nums, int k) {   //len是统计长度的，cnt是统计0的个数的long long len = 0,cnt = 0;long long left = 0,right = 0,n = nums.size();while(right < n){//1.进窗口if(nums[right] == 0)cnt+=1;//2.判断while(cnt > k){//出窗口if(nums[left++] == 0)cnt-=1;}//3.更新结果len = max(len,right-left+1);right++;}return len;}
};

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

解法：

先转变一下思路，将这道题换个思路。

这道题转化成了找一段最大连续区间，该区间内的和为sum-x。
三个关键点：1.最大的，2.连续区间，3.和为sum-x

解法：

• 1.暴力求解。
• 固定left指针，让right指针从left指针开始往后走，边走边将该元素添加到cnt，进行求和。当cnt > sum - x时，说明加多了不符合。此时清空cnt，让left+1，让right重新从left位置开始往后找。
  当找到cnt == sum - x时，统计长度。继续再次遍历。直到找到最大的len。
  注意，最后返回的是n - len(n为nums的大小）。
  以为我们只是把题目转化成了求最大连续区间的长度和为sum-x。
  但是题目的原意是求和为x的最小操作数，所以要返回n-len。

时间复杂度O(n^2)

• 2.滑动窗口

• 滑动窗口就是在暴力求解的基础上，当cnt > sum - x时，不需要让right重新往回走到left位置，而是让left往后走，也就是让left位置的元素出窗口。
  找到当cnt == sum - x时，更新长度。
  最后同样是返回n - len。

由于right无需重新从left位置开始遍历，所以时间复杂度O(n).

滑动窗口代码：

class Solution {
public:int minOperations(vector<int>& nums, int x) {int left = 0,right = 0,n = nums.size();int len = -1;int sum = 0;for(auto i : nums)sum += i;int target = sum - x;if(target < 0)return -1;sum = 0;while(right < n){//1.进窗口sum += nums[right];//2.判断while(sum > target){//出窗口sum -= nums[left++];}if(sum == target)len = max(len,right-left+1);right++;}return len == -1 ? -1 : n-len;}
};