题目描述
给定一个由若干 0 和 1 组成的数组 A ，我们最多可以将 K 个值从 0 变成 1 。
返回仅包含 1 的最长（连续）子数组的长度。
示例1
输入： A = [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] A[5] 和 A[10] 从 0 翻转到 1，最长的子数组长度为 6。
示例2
输入： A = [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] A[4] 、A[5] 和 A[9] 从 0 翻转到 1，最长的子数组长度为 10。
提示
- 1 <= A.length <= 20000
- 0 <= K <= A.length
- A[i] 为 0 或 1
题解
这题可以采用滑动窗口方法来求解。也就是用头尾指针 l 和 r ，初始化都是 l = r = 0 ，然后向右移动指针 r 。用变量 cnt0 记录 [l, r] 区间内有几个 0 ，用 res 保存答案。
如果 A[r] = 0 ，那就 0 的数量 cnt0 加 1 。并且 0 的数量和 K 判断，如果 cnt0 <= K ，那就说明 [l, r] 中间的 0 不多，可以用至多 K 次机会填充，那就继续向右移动 r 。但是如果 cnt0 > K ，那就说明 0 的数量太多了，得删掉点 0 了，这时候就得向右移动 l 。这时候看情况，如果 A[l] = 0 ，就要减小 cnt0 ，直到 cnt0 <= K 为止，不再移动 l 。然后继续移动 r ，重复上面过程即可。过程中时刻更新最长的距离 res 。
因为 l 和 r 分别最多移动 n 次，所以最终的时间复杂度是 的。
那么为什么这样是正确的呢？不会漏掉正确答案所在的区间吗？我们看看漏掉的是哪些区间。对于一个固定的 r ，移动 l 直到 0 的数量小于等于 K （记为 l' ）的过程中，漏掉的是 [<l, r] 和 [>l', r] 这些区间。前者 0 数量太多，不符合题意；后者长度更小，显然不是答案。然后继续右移 r ，直到第一个 0 数量大于 K 的位置，漏掉了 [<l, >r] 和 [>l, >r] 区间。前者 0 的数量一定大于 K ，为什么呢？因为右端点在 r 的时候， l 已经是最靠左使得 0 数量小于等于 K 的位置了，而现在 r 向右移动了， l 更不可能左移了；后者长度更小，不予考虑。综上考虑，最优的区间一定被考虑充分了。
代码
class Solution { public: int longestOnes(vector<int>& A, int K) { int n = A.size(); int l = 0, r = 0, cnt0 = 0, res = 0; while (r < n) { if (!A[r]) { cnt0++; while (cnt0 > K && l <= r) { if (!A[l++]) cnt0--; } } res = max(res, r - l + 1); r++; } return res; }
