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
  2. 输出：6
  3. 解释： 
  4. [1,1,1,0,0,1,1,1,1,1,1]
  5. 粗体数字从 0 翻转到 1，最长的子数组长度为 6。
输入：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。

解答 & 代码

本题相当于：子数组内最多可以包含 k 个 0，求最长子数组的长度
解法：滑动窗口 

class Solution {
public:
    // 本题转换为：子数组内最多可以包含 k 个 0，求最长子数组的长度
    int longestOnes(vector<int>& nums, int k) {
        int size = nums.size();
        int maxSubLen = 0;    // 满足条件的最大窗口长度
        int left = 0;        // 滑动窗口左边界
        int right = 0;        // 滑动窗口右边界
        int zeroCnt = 0;    // 当前窗口内 0 的个数
        // 当右边界没有走到数组尾部
        while(right < size)
        {
            if(nums[right] == 0)        // 如果右边界是 0，则窗口内 0 的个数 +1
                ++zeroCnt;
            // 如果窗口内 0 的个数大于 k，则不断右移左边界，直到窗口内 0 的个数小于 k
            while(zeroCnt > k)            
            {
                if(nums[left] == 0)
                    --zeroCnt;
                ++left;
            }
            // 更新满足条件的最大窗口长度
            maxSubLen = right - left + 1 > maxSubLen ? right - left + 1 : maxSubLen;
            // 窗口右边界右移
            ++right;
        }
        return maxSubLen;
    }
};

执行结果：

执行结果：通过

执行用时：52 ms, 在所有 C++ 提交中击败了89.80% 的用户
内存消耗：54.2 MB, 在所有 C++ 提交中击败了 14.55% 的用户