leetcode 1004. 最大连续1的个数 III（优质解法）

代码：

class Solution {
    public int longestOnes(int[] nums, int k) {
        int length=nums.length;
        int zero=0; //计数器，计数翻转 0 的个数
        int max=0;  //记录当前获得的最长子数组长度
        for(int left=0,right=0;right<length;right++){
           if(nums[right]==0){
               zero++;
               while (zero>k){
                   if(nums[left]==0){
                       zero--;
                   }
                   left++;
               }
               //zero<=k
           }
           //nums[right]==1
            max=Math.max(max,right-left+1);
        }
        return max;
    }
}

题解：

        首先，我们可以思考一下这个题的题意，题目要求找到数组中连续 1 的最大个数，由于需要连续的数据，说明需要我们找到的是连续 1 的 “子数组” ，而存在翻转 0 的机制，所以我们找到的子数组中最大可容纳 k 个 0 

        那么我们可以想到这个题的暴力解法，就是遍历获得所有的子数组，去除掉含 k 个 0 以上的子数组，在剩余的子数组中找到长度最长的子数组

        关于子数组以及子串的问题，我们很容易想到通过滑动窗口 - 双指针的方式解决

        我们通过示例 1 来进行分析：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2        

        将指针 L 和 R 指向 下标 0 的位置，L 和 R 指针之间的数据便是我们此时要讨论的子数组，首先，判断 R 指针指向的数据，数据为 1 ，那么此时我们不需要进行字符翻转，记录当前子数组的长度，让 R++ ,扩大我们讨论的子数组长度

1        1        1        0        0        0        1        1        1        1        0

L 

R

        当 R 指针指向 1 ，我们只需要和上述条件一样，记录当前子数组的长度（当前长度与之前保存的长度进行比较，取较大的保存），让 R++ ,扩大我们讨论的子数组长度即可，一直扩大到 R 指针指向 0 

        此时我们讨论的子数组中出现 0 了，但题目有字符翻转的机制，所以我们可以将当前遇到的 0 翻转为 1，我们通过一个计数器 zero ，记录我们已经翻转的 0 的个数，此时 zero = 1 （不会有小可爱真的把源数据改为 1 把），只有 zero > k 时才代表我们已经不能进行翻转，将 0 翻转为 1 后，我们同样记录当前讨论的子数组的长度，再让 R++ ，继续扩大我们讨论的子数组长度 

1        1        1        0        0        0        1        1        1        1        0

L 

                              R 

        当 R 指针指向当前位置时，计数器 zero 中的值为 3 ，已经大于 k 了，所以 R 指针此时指向的 0 ，我们不能进行翻转，这也代表以 L 指针为首位的子数组的最长长度我们已经获得了，此时我们可以让 L ++ ，讨论以下一个元素为首位的子数组的最长长度

1        1        1        0        0        0        1        1        1        1        0

L 

                                                   R    

        现在出现一个问题，我们需要让 R 指针回到 L 指针的位置，从头开始讨论子数组的最长长度吗？答案是不需要，因为 R 指针到达当前位置，0 的个数才增多，子数组才不符合要求，这也代表，R 指针之前的数据都是符合要求的，即使我们让 R 指针回到 L 指针的位置从头开始讨论，R 指针也一定会移动到当前位置，所以没有必要让 R 指针回去，此时 zero =3 不符合要求，我们让 L ++ 直到符合要求为止

1        1        1        0        0        0        1        1        1        1        0

          L         

                                                   R

        当 L 指针移动到当前位置时，zero = 2 = k，符合要求，记录当前讨论的子数组的长度，就可以让 R ++，继续扩大我们讨论的子数组长度 

1        1        1        0        0        0        1        1        1        1        0

                                        L         

                                                   R

        接下来的操作就是循环，直到 R 指针移动到当前位置，R = nums.length，就结束循环，得到了最长的子数组长度

1        1        1        0        0        0        1        1        1        1        0

                                                   L      

                                                                                                            R