算法练习：1004. 最大连续1的个数 III

题目链接：1004. 最大连续1的个数 III。

题目要求，给定一个数组，这个数组里面只有0或1，然后计算有多少个连续的1的最大长度，同时给了一个条件就是，可以把k个0变成1，然后来计算长度。

暴力解法：枚举每一个子数组，记录连续为1的长度，同时用一个计数器cut来统计0的个数。

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int n = nums.size();
        int sum = INT_MIN;
        for(int i = 0;i < n;i++)
        {
            int cut = 0;
            int sum1 = 0;
            for(int j = i;j < n;j++)
            {
                if(nums[j] == 0)
                {
                    cut++;
                }
                if(cut == k+1)
                {
                    break;
                }
                sum1++;
            }
            sum = sum1 > sum ? sum1 : sum;
        }
        return sum;
    }
};

但是暴力解法会超时！！！

在暴力解法前提下进行对代码的优化：

• 通过定义两个指针来控制，left固定在第一个位置，right进行移动，定义cut当计数器
• 如果right对应值为1，则无视，直接++
• 如果right对应值为0，则cut++，right也++
• 判断，如果cut > k，则开始移动left
• 如果left对应值为1，无视，直接++
• 如果对应值为0，则cut--，left也++
• 判断完就进行更新长度

为什么判断cut > k后要进行移动left，而right不动，因为left到right之间0的个数已经超过k，此时right在回到left位置重新进行检测长度，没有必要，因为重新检测的长度肯定比之前长度短，所以只需要更新left，更新到cut=k的位置，然后再进行移动right。

这样同向双指针操作叫做滑动窗口。

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left = 0,right = 0,cut = 0;
        int n = nums.size();
        int ret = 0;
        while(left<n && right < n)
        {
            if(nums[right] == 0) cut++;
            while(cut > k)
            {
                if(nums[left] == 0) cut--;
                left++;
            }
            ret = max(ret , right - left + 1);
            right++;
        }
        return ret;
    }
};