【C++算法】11.滑动窗口_最大连续1的个数lll

---

题目链接：

1004. 最大连续 1 的个数 III

---

题目描述：

---

解法

解法一：暴力枚举+zero计数器

转化找出最长的子数组，0的个数不超过k个。

例如：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2

解法二：滑动窗口

1. left = 0，right = 0

2. 进窗口：left指向1无视，指向0计数器+1

3. 判断（0的个数>k）->出窗口，不断循环

4. 更新结果

5. 等到right指向最后的时候，结束更新

---

C++ 算法代码：

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

---

图解

例如：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2

1. ret = 0,left = 0, right = 0, zero = 0，ret = max(ret, right - left + 1) = 1，right++,right = 1

2. ret = 1,left = 0, right = 1, zero = 0，ret = max(ret, right - left + 1) = 2，right++,right = 2

3. ret = 2,left = 0, right = 2, zero = 0，ret = max(ret, right - left + 1) = 3，right++,right = 3

4. ret = 3,left = 0, right = 3, zero = 0，nums[right] == 0 ->zero++,zero=1

   ret = max(ret, right - left + 1) = 4，right++,right = 4

5. ret = 4,left = 0, right = 4, zero = 1，nums[right] == 0 ->zero++,zero=2

   ret = max(ret, right - left + 1) = 5，right++,right = 5

6. ret = 5,left = 0, right = 5, zero = 2，nums[right] == 0 ->zero++,zero=3

   while(zero > k){ // 判断if(nums[left++] == 0){zero--;}
   }
   

   zero = 2,left = 4

   ret = max(ret, right - left + 1) = 5，right++,right = 6

7. 后面流程一样，就不多赘述了。