LeetCode 分类刷题：1004. 最大连续1的个数 III

题目

给定一个二进制数组 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。

解析

力扣官网中，本题提示如下图：

统计窗口内 0 的个数 cnt0​，则问题转化成在 cnt0​≤k 的前提下，窗口大小的最大值。

作者：灵茶山艾府
链接：https://leetcode.cn/problems/max-consecutive-ones-iii/solutions/2126631/hua-dong-chuang-kou-yi-ge-shi-pin-jiang-yowmi/
来源：力扣（LeetCode）

答案

/*** @param {number[]} nums* @param {number} k* @return {number}*/
var longestOnes = function(nums, k) {let left = 0, ans = 0, count = 0;    //初始化左指针，最大长度和记录0的个数的变量for(let right = 0; right < nums.length; right++) {    //移动右指针if(nums[right] === 0) count++;    //更新窗口内0的个数if(count > k) {    //0的个数超过kwhile(nums[left] !== 0) left++;    //缩小窗口，找到元素为0的最左端left++, count--;    //左指针移动到下一个不为0的位置，0的个数减一}ans = Math.max(ans, right - left + 1);    //更新最大长度}return ans;
};

复杂度分析

时间复杂度：O(n)，其中 n 为 nums 的长度。

空间复杂度：O(1)。