LeetCode 1004. 最大连续1的个数 III(滑动窗口)

题目

给定一个由若干 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] 粗体数字从 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] 粗体数字从 0 翻转到 1，最长的子数组长度为 10。

提示：

1 <= A.length <= 20000 0 <= K <= A.length A[i] 为 0 或 1

思路

采用滑动窗口双指针： 定义nmax记录窗口最大值，left、right指针指向窗口左右端。 循环遍历数组，每次循环让right指针右移一位。 if (A[i] == 0)就让k--，当A[i] == 0时 if (k != 0)则继续下一轮循环。 当k == 0时，nmax = max(nmax, right - left);将nmax进行赋值，right - left为当前窗口的长度，然后让left指针指到当前窗口的第一个0的下一位(从窗口中抛弃第一个0来让k + 1，从而能让下一个0变成1)。

最后再对nmax进行一次赋值，因为可能出现数组已经遍历完但k != 0的情况。

class Solution {
public:
    int longestOnes(vector<int>& A, int K) {
        int nmax = 0, k = K, left = 0, right = 0;
        for (int i = 0; i < A.size(); i++, right++) {
            if (A[i] == 0) {
                if (k == 0) {
                    nmax = max(nmax, right - left);
                    while (A[left] != 0 && left <= right) {
                        left++;
                    }
                    k++;
                    left++;
                }
                k--;
            }
        }
        nmax = max(nmax, right - left);
        return nmax;
    }
};