「优选算法刷题」：最大连续1的个数

一、题目

给定一个二进制数组?nums?和一个整数?k，如果可以翻转最多?k?个?0?，则返回?数组中连续?1?的最大个数?。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

二、思路解析

老规矩，求一段连续区间，一眼就要想到 滑动窗口 。

而题目要求的 「数组中连续?1?的最大个数」，我们也可以等价转换成：求数组中?段最长的连续区间，要求这段区间内?0 的个数不超过?k 个。

具体实现如下：

三、完整代码

class Solution {
    public int longestOnes(int[] nums, int k) {
        int left = 0;
        int right = 0;
        int zero = 0;
        int ret = 0;
        int n = nums.length;
    
        for(;right < n;right ++){
            if(nums[right] == 0 ){
                zero++;
            }
            while(zero > k){
                if(nums[left++] == 0){
                    zero--;
                }
            }
            ret = Math.max(ret,right-left+1);
        }
        return ret;
    }
}

以上就是本篇博客的全部内容啦，如有不足之处，还请各位指出，期待能和各位一起进步！