Leetcode每日刷题之1004.最大连续1的个数|||(C++)
1.题目解析
本题的目的是找出能最多翻转k个0的情况下最长连续的1的个数，并且这是一个二进制数组，只存在0和1，翻转0就是将0变为1
2.算法原理
首先我们想到的一定是暴力枚举，即依次列举出在最多翻转k个0的情况下所有连续1的子数组的长度，求出最大值，这样的时间复杂度会很高，所以我们可以换一个思路，即找出子数组满足其中的0的个数小于k，此时我们直接求该子数组的长度就代表了连续1的个数，此时只要求出一个子数组其中含有0的个数zero<k且是满足该条件的最长子数组即可
这里我们用到的是"滑动窗口"来解决问题，即固定一个指针left后移动right指针并统计right指针遇到0的个数，此时就是入窗口的操作，然后当zero>k时就需要移动left指针直到zero<=k，这一步是出窗口的操作，然后更新数据即最大子数组长度即可
3.代码展示
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int len = 0;int n = nums.size();for(int left = 0,right = 0,zero = 0;right < n;right++){if(nums[right] == 0){zero++;}while(zero > k){if(nums[left++] == 0){zero--;}}len = max(len,right - left + 1);}return len;}
};