文章目录
- 1.题目
- 2.思路
- 3.代码
1.题目
1004. 最大连续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。
2.思路
找出最长子数组，0的个数不超过K个,
right指针向右扩展窗口，寻找满足条件的子区间。- 当窗口不再满足条件时，通过移动
left指针来缩小窗口，使其重新满足条件。
3.代码
class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left = 0, right = 0;int len = 0;while (right < nums.size()) {// 当遇到0时，减少k，表示翻转了一个0if (nums[right] == 0) {--k;}++right;// 当翻转的0超过k时，移动left指针收缩窗口while (k < 0) {if (nums[left] == 0) {++k;}left++;}// 更新窗口内连续1的最大长度len = max(len, right - left);}return len;}
};
