本文主要是介绍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;}
};
总结：
这题是一个很经典的滑动窗口的问题，结合我们之前做的滑动窗口的问题来看，滑动窗口出现的场景通常需要枚举数组所有情况，也就是暴力，然后我们在暴力的基础上进行优化。
这篇关于LeetCode-1004. 最大连续1的个数 III的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
