【LeetCode: 1004. 最大连续1的个数 III + 滑动窗口】

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域优质创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚩 题目链接

• 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

🌟 求解思路&实现代码&运行结果

⚡ 滑动窗口

🥦 求解思路

1. 滑动窗口：使用滑动窗口的思想，维护一个窗口 [left, right]，使得窗口内最多包含 k 个 0。

2. 统计 0 的数量：

   • 遍历数组，当遇到 0 时，增加 zero 的计数。

   • 如果 zero 的数量超过 k，则移动左指针 left，直到 zero 的数量不超过 k。

3. 更新最大长度：在每次遍历时，更新窗口的最大长度 max。

4. 有了基本的思路，接下来我们就来通过代码来实现一下。

🥦 实现代码

class Solution {
    public int longestOnes(int[] nums, int k) {
        int n = nums.length;
        int left = 0;
        int zero = 0, max = 0;
        for (int right = 0; right < n; right++) {
            int x = nums[right];
            if (x == 0) zero++;
            while (zero > k) {
                int y = nums[left++];
                if (y == 0) zero--;
            }
            max = Math.max(max, right - left + 1);
        }
        return max;
    }
}

🥦 运行结果

💬 共勉