1.题目
题目分析:
给一个数字k,可以把数组里的0改成1,但是只能改k次,然后该变得到的数组能找到最长的子串且都是1。
2.算法原理
这里不用真的把0变成1,因为改了比较麻烦,下次用就要改回成1,这里用滑动窗口来,先进窗口,遇到1就无视,遇到0就进窗口,虽然1和0都在一个窗口中在画图里,但是要把1看出空气,理会0的个数,然后更k比较,满了就开始出窗口了,要排除0直到窗口内的0个数小于k。for循环来移动right,遇到1是无视,就走for循环来,遇到0就特殊处理,每次循环都更新长度值。
3.代码实现
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n=nums.size();int len=0;for(int left=0,right=0,zero=0;right<n;right++){//等于1不用管,for循环会自动right++if(nums[right]==0) zero++;while(zero>k){if(nums[left++]==0) zero--;}len=max(len,right-left+1);}return len;}
};