????题目描述:
给定一个二进制数组 nums
和一个整数 k
,如果可以翻转最多 k
个 0
,则返回 数组中连续 1
的最大个数 。
示例 1:
输入:nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], K = 2
输出:6
解释:[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
粗体数字从 0 翻转到 1,最长的子数组长度为 6。
示例 2:
输入:nums = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1], K = 3
输出:10
解释:[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1]
粗体数字从 0 翻转到 1,最长的子数组长度为 10。
????代码实现:
class Solution
{
public:
int longestOnes(vector<int>& nums, int k)
{
int sumzero = 0;
int len = 0;
for(int left = 0, right = 0; right <nums.size(); ++right)
{
if(nums[right] == 0) ++sumzero;
while(sumzero > k)
if(nums[left++] == 0) --sumzero;
len = max(len, right - left + 1);
}
return len;
}
};
????代码解析:
我们可以对问题进行深入理解理解,首先题目所讲的是K,它是一个最大的范围,我们可以翻转1次也可以翻转K - 1次也都可以。
如果用暴力来解决这道题的话,就需要一个一个的将0转换成1,这样子的话代码实现过于复杂了。
我们可以简化一下题目描述,我们其实想找到的是一个子数组,这一个子数组中有K个0或K个以下数的0变成1后能满足最大的长度。
所以我们只需要通过left指针和right指针
遍历这个数组,统计0的个数,然后判断是否超过了K,如果超过了K就记录这个长度,然后再让left++
让right回来继续遍历,然后一个一个的判断。这其实也是一种暴力解法,但是好在我们把问题简化了。
现在我们可以来尝试模拟一遍:
如果此时我们对0的个数进行统计之后,结果大于k了:
我们left++
然后再让right回到left这里:
那当我们的right还是会经过那两个0,我们又要再让left++
,right也又要回来
这不是上面那个《无重复字符的最长子串》和《长度最小的子数组》结合起来后的题目嘛?
当我们的0的个数大于2时,我们就没必要再让right回来了,只要让left一直向右移,遇到0就让统计0的个数的变量减一,知道正好等于就让left停下来,然后再进行判断。这不就是滑动窗口嘛。