【LeetCode】1004. Max Consecutive Ones III 最大连续1的个数 III（Medium）（JAVA）

【LeetCode】1004. Max Consecutive Ones III 最大连续1的个数 III（Medium）（JAVA）

题目地址: https://leetcode.com/problems/max-consecutive-ones-iii/

题目描述：

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s.

Example 1:

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
Output: 6
Explanation:
[1,1,1,0,0,1,1,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Example 2:

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
Output: 10
Explanation:
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
Bolded numbers were flipped from 0 to 1. The longest subarray is underlined.

Note:

1. 1 <= A.length <= 20000
2. 0 <= K <= A.length
3. A[i] is 0 or 1

题目大意

给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。

返回仅包含 1 的最长（连续）子数组的长度。

解题方法

1. 用前缀和 P(i) 表示 [0, i] 前 i 个元素的和。
2. P(right) - P(left) 表示 [left, right] 区间内的和，(right - left + 1) - (P(right) - P(left)) 表示区间内 0 的个数
3. 只要区间内 0 的个数小于等于 K, 这个区间就是一个连续子数组
4. 所以采用滑动窗口的思想，不断找出 left 和 right, 然后计算出窗口的长度

class Solution {
    public int longestOnes(int[] A, int K) {
        int left = 0;
        int right = 0;
        int lSum = 0;
        int rSum = 0;
        int res = 0;
        for (right = 0; right < A.length; right++) {
            rSum += 1 - A[right];
            while (rSum - lSum > K) {
                lSum += 1 - A[left];
                left++;
            }
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}

执行耗时:4 ms,击败了47.01% 的Java用户
内存消耗:40 MB,击败了11.37% 的Java用户

欢迎关注我的公众号，LeetCode 每日一题更新