题目链接
题目简介
给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长（连续）子数组的长度。
示例 1：
输入：A = [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：
输入：A = [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。
题目解析
- 我们可以将K个值为0的转成K个值为1的，求一个连续数组，里面
包含的1是最多的 - 我们可以使用滑动窗口进行解决
- 我们定义 left 和 right 分别代表滑动窗口的两端
- right 主动右移：right 指针每次移动一步。当 A[right] 为 0，说明滑动窗口内增加了一个 0；
- left 主动右移：判断此时窗口内 0 的个数，如果超过了 K，则 left 指针被迫右移，直至窗口内的 0 的个数小于等于 K 为止。
- 每次都求出 max，返回即可
题目代码
class Solution { public int longestOnes(int[] A, int K) { int len = A.length; int left = 0; int right = 0; int res = 0; int sum = 0; while(right < len){ // 记录当前滑动窗口内含有多少0 if(A[right] == 0){ sum++; } right++; // 如果当前滑动窗口中的 0 超过 K 个，则需要考虑 left 的坐标 while(sum > K){ // 如果下一个为 0 的话,则区间内需要去除一个 0 if(A[left] == 0){ sum--; } left++; } res = Math.max(res, right - left); } return res; } }
