LeetCode-1004. 最大连续1的个数 III

每日一题系列（day 20）

前言：

🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈 🌈

🔎🔎如果说代码有灵魂，那么它的灵魂一定是👉👉算法👈👈，因此，想要写出💚优美的程序💚，核心算法是必不可少的，少年，你渴望力量吗😆😆，想掌握程序的灵魂吗❓❗️那么就必须踏上这样一条漫长的道路🏇🏇，我们要做的，就是斩妖除魔💥💥，打怪升级！💪💪当然切记不可😈走火入魔😈，每日打怪，拾取经验，终能成圣🙏🙏！开启我们今天的斩妖之旅吧！✈️✈️

题目：

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回数组中连续 1 的最大个数。

示例1：

在这里插入图片描述
示例2：

在这里插入图片描述
提示：

1 <= nums.length <= 105
nums[i] 不是 0 就是 1
0 <= k <= nums.length

解法一（暴力枚举）：

首先分析题目，给定k个数，可以将数组里的0翻转为最多k个1，并且要求返回翻转后最长1的子数组。如果我们直观上来看的话，翻转0为最长子数组的情况可能不止一种，但是我们子数组最长的长度却是不变的。
所以当翻转0的位置不同时，但是却造成了最长子数组长度相同，我们就不用管0翻转的顺序了。

但是我们如何找出这个最长子数组呢？既然是数组，我们不妨可以枚举出所有情况，最后在返回最长子数组。
既然要确定子数组的长度，那么就一定要有两个指针在数组上遍历，由于0的个数有限制，所以我们可以考虑使用计数器来统计0的个数，而被统计的0就相当于翻转成为了1。
当0的个数超出限制后，我们本次遍历结束，在全局范围内设置一个ret变量接收本次遍历的最长子数组。左指针向后移动一位，右指针重置，开启第二轮遍历，直到遍历完。

这里也可以优化一下，如果数组当中0的个数小于等于k，那么就相当于整个数组皆可以翻转，直接返回整个数组的长度即可。

代码演示：

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int sum_one = 0;//统计最长的1的子数组长度
        int sum_zero = 0;//统计0的个数

        for(int i = 0; i < nums.size() ; ++i) if(nums[i] == 0) sum_zero++;//0的个数

        if(sum_zero <= k) return nums.size();//k多0少的情况

        for(int i = 0 ; i < nums.size() ; ++i)//正常情况，i相当于左指针
        {
            int cnt = k;//将k赋值为cnt，当cnt >= 0 时为合法范围
            for(int j = i ; j < nums.size() ; ++j)//右指针移动
            {
                if(nums[j] == 0)//当数组元素为0时，翻转
                {
                    cnt--;
                }
                if(cnt >= 0)//符合条件每次都计算长度
                {
                    sum_one = max(j - i + 1, sum_one);//下标从0开始的，所以要加一
                }
            }
        }
        return sum_one;
    }
};

在这里插入图片描述
但是这种暴力解法在本题时跑不过的，时间限制原因，所以我们只有另想他法，尽量去优化时间复杂度。

解法二（滑动窗口）：

虽然暴力枚举不能通过测试用例，但是也给我们提供了良好的思路，用双指针来解决问题，我们来分析上面的暴力解法有什么不妥？

首先，我们其实没有必要全枚举，如果当右指针遇到0的时候，如果我们回退到i + 1的位置，那么从i + 1到上一次遍历的最远位置不就重新遍历了一遍？这种多余的遍历我们并不需要。
所以当右指针遇到0的个数满了的时候，我们将左指针进行右移。
加上了这一步，我们就可以将时间复杂度从O(n^2)降为O(n)了。最后需要注意的是，如果当左指针走过0的时候，我们最长子数组里面就少了个0，这个时候我们的计数器就该减去1了，每次循环我们都进行判断最长子数组。最后返回即可。

代码演示：

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int ret = 0;
        int sum_zero = 0;
        for(int left = 0, right = 0; right < nums.size() ; ++right)
        {
            if(nums[right] == 0) sum_zero++;//统计翻转0个数
            while(sum_zero > k)//个数超了后移动左指针
            {
                if(nums[left++] == 0) sum_zero--;//越过0，子数组中的0就减少了，所以计数器也要自减
            }
            ret = max(ret, right - left + 1);//返回最终结果
        }
        return ret;
    }
};