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 <= nums.length <= 10⁵
nums[i] 不是 0 就是 1
0 <= k <= nums.length

2.思路

（1）前缀和

（2）前缀和 & 二分搜索

（3）滑动窗口

3.代码实现（Java）

//思路1————前缀和
class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        /* 
            preSum[i] 表示 nums[0...i - 1] 的累加和
            preSum[j + 1] - preSum[i] 为 nums[i...j] 的累加和
        */
        int[] preSum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = n; j >= i + 1; j--) {
                // nums[i...j - 1]
                int len = j - i;
                if (len - (preSum[j] - preSum[i]) <= k) {
                    res = Math.max(res, len);
                    break;
                }
            }
            if (res >= n - i) {
                break;
            }
        }
        return res;
    }
}

//思路2————前缀和 & 二分搜索
class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        /*
            preSum[i] 表示 nums[0...i - 1] 中 0 的个数
            preSum[j + 1] - preSum[i] 为 nums[i...j] 中 0 的个数
        */
        int[] preSum = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + (1 - nums[i - 1]);
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            int left = binarySearch(preSum, preSum[i + 1] - k);
            res = Math.max(res, i - left + 1);
        }
        return res;
    }

    //查找 target 在 nums 中的左边界
    public int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

}

//思路3———滑动窗口
class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int left = 0;
        int leftCnt = 0;
        int rightCnt = 0;
        int res = 0;
        for (int right = 0; right < n; ++right) {
        	// rightCnt 记录 nums[0...right] 中 0 的数量
            rightCnt += 1 - nums[right];
            while (rightCnt - leftCnt > k) {
	            // leftCnt 记录 nums[0...left] 中 0 的数量
                leftCnt += 1 - nums[left];
                left++;
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}