一、题目描述

1004.最大连续1的个数III leetcode

二、算法原理

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

• 解法一：暴力枚举 + zero计数器
• 解法二：利用“滑动窗口”解决
  • 1. left = 0 ， right = 0
  • 2. 进窗口（如果是1，无视；如果是0，计数器+1）
  • 3. 判断（zero > k  ）
    • 出窗口
  • 4. 更新结果

三、代码实现

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;
    }
};