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。
提示：
1 <= nums.length <= 105
nums[i] 不是 0 就是 1
0 <= k <= nums.length
2.解法（滑动窗⼝）：
算法思路：
不要去想怎么翻转，不要把问题想的很复杂，这道题的结果⽆⾮就是⼀段连续的 1 中间塞了 k 个0 嘛。
因此，我们可以把问题转化成：求数组中⼀段最⻓的连续区间，要求这段区间内 0 的个数不超
过 k 个。既然是连续区间，可以考虑使⽤「滑动窗⼝」来解决问题。
算法流程：
a. 初始化⼀个⼤⼩为 2 的数组就可以当做哈希表 hash 了；初始化⼀些变量 left = 0 ,right = 0 ,ret = 0 ；
b. 当 right ⼩于数组⼤⼩的时候，⼀直下列循环：
i. 让当前元素进⼊窗⼝，顺便统计到哈希表中；
ii. 检查 0 的个数是否超标：
• 如果超标，依次让左侧元素滑出窗⼝，顺便更新哈希表的值，直到 0 的个数恢复正
常；
iii. 程序到这⾥，说明窗⼝内元素是符合要求的，更新结果；
iv. right++ ，处理下⼀个元素；
c. 循环结束后， ret 存的就是最终结果。
2.图解
3.代码实现
1.C语言
// 辅助函数，返回两个整数的最大值 int max(int a, int b) { return (a > b) ? a : b; } // 主函数 int longestOnes(int* nums, int numsSize, int k) { int ret = 0; int left = 0, right = 0, zero = 0; for (right = 0; right < numsSize; right++) { if (nums[right] == 0) { zero++; // 进窗口 } while (zero > k) { // 判断条件 if (nums[left] == 0) { zero--; // 出窗口 } left++; } ret = max(ret, right - left + 1); // 更新结果 } return ret; }
2.C++
class Solution { public: int longestOnes(vector<int>& nums, int k) { int ret = 0; for (int left = 0, right = 0, zero = 0; right < nums.size(); right++) { if (nums[right] == 0) zero++; // 进窗⼝ while (zero > k) // 判断 if (nums[left++] == 0) zero--; // 出窗⼝ ret = max(ret, right - left + 1); // 更新结果 } return ret; } };
