最大连续1的个数 III

给定一个由若干 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。

---

解题思路

子数组(滑动窗口)双指针：left 指针和 right 指针，开始时均指向数组 A 的开头。
最大连续 1 的个数，最多可以将 K 个值从 0 变成 1 <==> 找到一个长度最长的子数组，并且子数组中 0 的个数不超过 K。

1. 判断当前 right 指针指向的元素值是否是 0：若值为 1，则直接使 right 指针右移一位；若值为 0，则令 count (用来记录当前子数组中出现的 0 的个数)的值加 1。

2. 判断 count 和 K 的大小：若 count > K，先要看 left 指针当前指向的元素值是否为 0 (这里可以使用昨天使用的异或运算符 ^，这样会减少程序运行的时间)：若值为 0，则要使 count 的值减 1，然后再使 left 指针向右移动一位；若值为 1，则不需要修改 count 值，只需要将 left 指针右移一位，然后继续执行第三步。若 count <= K，则不需要操作直接进行第三步即可。

3. 比较当前窗口的大小与 maxLength (用来存储符合条件的最长连续子数组的长度的)，然后 right 指针右移一位。

用 for 循环比用 while 循环更快一些。

---

代码

class Solution {

    public int longestOnes(int[] A, int K) {

        int n = A.length;
        int left = 0, right = 0;
        int maxLength = 0;
        int count = 0;

        for (right=0;right<n;right++) {

            if (A[right] == 0) {

                count++;
            }
            //因为是count++后接着进行判断，所以可以用if
            if (count > K) {
                
                //异或操作：A[left] == 1时返回0；A[left] == 0时返回1。
                count -= A[left] ^ 1;
                left++;
            }
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}

时间复杂度：因为 A 数组遍历了一次且长度为 n，所以复杂度为O(n)
空间复杂度：因为没有开辟新的空间，复杂度为O(1)