1004. 最大连续1的个数 III #

标签：双指针、滑动窗口
难度：中等

题目大意 #

描述：给定一个由 0、1 组成的数组 nums，再给定一个整数 k。最多可以将 k 个值从 0 变到 1。

要求：返回仅包含 1 的最长连续子数组的长度。

说明：

$1 \le nums.length \le 10^5$。
nums[i] 不是 0 就是 1。
$0 \le k \le nums.length$。

示例：

示例 1：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


输入：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]
将 nums[5]、nums[10] 从 0 翻转到 1，最长的子数组长度为 6。


输入：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]
将 nums[4]、nums[5]、nums[9] 从 0 翻转到 1，最长的子数组长度为 10。

解题思路 #

思路 1：滑动窗口（不定长度） #

使用两个指针 left、right 指向数组开始位置。使用 max_count 来维护仅包含 1 的最长连续子数组的长度。
不断右移 right 指针，扩大滑动窗口范围，并统计窗口内 0 元素的个数。
直到 0 元素的个数超过 k 时将 left 右移，缩小滑动窗口范围，并减小 0 元素的个数，同时维护 max_count。
最后输出最长连续子数组的长度 max_count。

思路 1：代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def longestOnes(self, nums: List[int], k: int) -> int:
        max_count = 0
        zero_count = 0
        left, right = 0, 0
        while right < len(nums):
            if nums[right] == 0:
                zero_count += 1
            right += 1
            if zero_count > k:
                if nums[left] == 0:
                    zero_count -= 1
                left += 1
            max_count = max(max_count, right - left)
        return max_count

思路 1：复杂度分析 #

时间复杂度：$O(n)$。
空间复杂度：$O(1)$。