难度：★★★☆☆
类型：数组
方法：前缀和，二分法，滑动窗口

题目

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给定一个由若干 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

解答

方法1：前缀和

我们只关心0的分布，一段区间内0的个数是我们最关心的，我们可以准备一个前缀和列表prefix_sum，其中每个位置i处的值表示A[:i]中的0的个数，这样通过不同位置处的列表值相减，可以快速获得区间中的零的个数。

假设翻转后最长的1的子串以左右指针为边界，遍历右指针，通过使用二分法，可以快速定位与右指针所在位置，通过差值计算可以快速获取左指针应该在的位置，从而确定每种右指针情况下的左指针的最佳位置。

from bisect import bisect_left


class Solution:
    def longestOnes(self, A, K):
        n = len(A)
        prefix_sum = [0]
        for num in A:
            prefix_sum.append(prefix_sum[-1] + (1 - num))

        ans = 0
        for right in range(n):
            left = bisect_left(prefix_sum, prefix_sum[right + 1] - K)
            ans = max(ans, right - left + 1)

        return ans

方案2：滑动窗口

如果我们将寻找左指针的过程做一个优化，不用滑动窗口，而采用遍历查询的方式实现，可以在某种程度上降低计算复杂度。

我们需要维护一个窗口，窗口中的零的个数不超过K，每当一旦超过K，则左指针及时向右滑动，直到窗口中零的个数保持在K为止。这样也可以获得每种右指针情况下的左指针的最佳位置，注意区间长度为右指针-左指针+1.

class Solution:
    def longestOnes(self, A, K):

        left = 0
        ans = 0
        zeros_in_window = 0
        for right in range(len(A)):
            if A[right] == 0:
                zeros_in_window += 1
                while zeros_in_window > K:
                    if A[left] == 0:
                        zeros_in_window -= 1
                    left += 1
            ans = max(ans, right-left+1)
        return ans

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析