LeetCode_前缀和_滑动窗口_中等_1004.最大连续1的个数 III

骑猪看日落 2023-10-12 21:59 44阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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 <= 105  
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;
                    /* 
                    	preSum[j] - preSum[i] 表示 nums[j - 1...i] 中 1 的数量
                    	len - (preSum[j] - preSum[i] 表示 nums[j - 1...i] 中 0 的数量
    				*/
                    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 right = 0;
            int leftCnt = 0;
            int rightCnt = 0;
            int res = 0;
            while (right < n) {
        
                // rightCnt 记录 nums[0...right] 中 0 的数量
                rightCnt += 1 - nums[right++];
                while (rightCnt - leftCnt > k) {
        
                    // leftCnt 记录 nums[0...left] 中 0 的数量
                    leftCnt += 1 - nums[left++];
                }
                res = Math.max(res, right - left);
            }
            return res;
        }
    }