力扣—最大连续1的个数 III

题目解析

给定一个二进制数组 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。

提示：

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

解题思路

我们通过示例一和示例二可以发现在翻转的数组里都翻转了K个0得到最大连续1的个数，所以我们可以把问题转化为找一个连续的子数组使其中包含0的个数为K个。这样一来我们就可以用滑动窗口的思路，用滑动窗口这个思路时 一定要确保两个指针同向移动。
用代码来展示思路

class Solution {
    public int longestOnes(int[] nums, int k) 
    {
        int ret=0;
     for(int right=0,left=0,sum=0;right<nums.length;right++)
     {
        if(nums[right]==0) sum++;
        while(sum>k)
        {
            if(nums[left++]==0)
            {
                sum--;
            }
        }
        ret=Math.max(ret,(right-left+1));
     }
     return ret;
    }
}

一、.初始化变量：
2.ret：用于存储最长的由1组成的子数组的长度。
3.right：右指针，用于遍历数组 nums。
4.left：左指针，用于标记当前子数组的起始位置。
5.sum：用于记录当前窗口中0的个数。
二、主循环：
1.for (int right = 0; right< nums.length; right++)：遍历数组，right 表示当前考虑的元素位置。
2.处理当前元素：
3.如果 nums[right] == 0，说明遇到了一个0，将 sum 增加。
三、.维护窗口：
1.while (sum>k)：当窗口中的0的个数超过了 k，需要收缩窗口。
2.if (nums[left++] == 0)：如果左指针处的元素是0，将 sum 减少，即表示移出了一个0。
3.这样通过移动左指针 left，缩小窗口，直到 sum 不大于 k 为止。
四、.更新最长子数组长度：
1.ret = Math.max(ret, (right - left + 1))：每次移动右指针 right 后，更新 ret，确保它始终记录窗口中的最大长度。
2.最终返回 ret，即为最长由1组成的子数组的长度，其中最多可以将 k 个0替换为1。
总结
通过维护一个窗口来动态地计算符合条件的子数组的长度。它的时间复杂度是 O(n)，其中 n 是数组 nums 的长度，因为每个元素最多被处理两次（一次加入窗口，一次移出窗口）。

代码实现

Java实现

class Solution {
    public int longestOnes(int[] nums, int k) 
    {
        int ret=0;
     for(int right=0,left=0,sum=0;right<nums.length;right++)
     {
        if(nums[right]==0) sum++;
        while(sum>k)
        {
            if(nums[left++]==0)
            {
                sum--;
            }
        }
        ret=Math.max(ret,(right-left+1));
     }
     return ret;
    }
}

C语言

int longestOnes(int* nums, int numsSize, int k) 
{
    int ret=0;
	int left=0,right=0,sum=0;
	for(right=0;right<numsSize;right++)
	{
		if(nums[right]==0) sum++;
	    while(sum>k)
	    {
			if(nums[left++]==0)
			{
				sum--;
			}
		}
		ret=ret>(right-left+1)?ret:(right-left+1);
	}
	return ret;
}		

欢迎留言，点赞，收藏。