11.LeetCode 1004. 最大连续1的个数 III | 滑动窗口解法详解（Java）

目录

1. 题目解析

2. 算法原理 + 编写代码

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

解法二：滑动窗口

1. 题目解析

题目：1004. 最大连续1的个数 III

OJ链接：1004. 最大连续1的个数 III - 力扣（LeetCode）

给定一个二进制数组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. 算法原理 + 编写代码

转化思路：找出最长的子数组，其中0的个数不超过k个。

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

通过双重循环枚举所有子数组，统计每个子数组中0的个数，超过k则停止扩展，记录最大长度。

class Solution { public int longestOnes(int[] nums, int k) { int n = nums.length; int maxLen = 0; // 遍历所有可能的子数组起点i for (int i = 0; i < n; i++) { int zeroCount = 0; // 统计当前子数组中0的个数 // 遍历所有可能的子数组终点j（j >= i） for (int j = i; j < n; j++) { if (nums[j] == 0) { zeroCount++; } // 如果0的个数超过k，就不需要继续扩展j了（因为子数组是连续的，再往后j，0的个数只会更多 if (zeroCount > k) { break; } // 更新最大长度 maxLen = Math.max(maxLen, j - i + 1); } } return maxLen; } }

解法二：滑动窗口

通过维护一个滑动窗口，保证窗口内0的个数不超过k，逐步扩大窗口并更新最大长度。

步骤：

1. 初始化left = 0,right = 0,zero = 0。

2. 右指针right遍历数组，进窗口：若nums[right]为0，zero计数 +1。

3. 判断：若zero > k，则需要移动左指针left缩小窗口，出窗口：若nums[left]为0，zero计数 -1，左指针右移。

4. 更新结果：每次窗口合法时，更新最大长度ret = Math.max(ret, right - left + 1)。

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