# 1004. 最大连续 1 的个数 III
### 题目地址(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
```
### 前置知识
*
### 公司
* 暂无
### 思路
这道题我在 [字节跳动的算法面试题是什么难度？](https://lucifer.ren/blog/2020/09/06/byte-dance-algo-ex/) 提到过这道题的换皮题。大家可以将这两道题目结合起来理解。接下来，我们看下这道题如何解决。
如果题目没有`最多可以将 K 个值从 0 变成 1` 。这个条件，那么会很简单，是一个常规的滑动窗口模板题。 我们加上这个条件对问题有什么样的影响呢？
这道题我们只需要记录下加入窗口的是 0 还是 1：
* 如果是 1，我们什么都不用做
* 如果是 0，我们将 K 减 1
相应地，我们需要记录移除窗口的是 0 还是 1:
* 如果是 1，我们什么都不做
* 如果是 0，说明加进来的时候就是 0，加进来的时候我们 K 减去了 1，这个时候我们再加回去 1。
如果 K 减少到负数，则收缩窗口大小。不断用满足条件的窗口大小更新答案即可。
#### 为什么这种思路可行？
这其实就是滑动窗口的常见套路。 这种算法可行的根本原因在于其本身就是暴力枚举的优化。如果让你用最暴力的解法如何求解呢？无非就是枚举所有的子数组，这需要 $O(N^2)$ 的时间复杂度，接下来判断子数组是否满足**最多将 k 个 0 变成 1，子数组全部为 1**。如果满足则更新答案即可。 如何对暴力解进行优化呢？
比如现在是判断的子数组 A\[2:3]，我们计算出 A\[2:3] 有一个 0，也就是说需要将一个 0 变成 1 才行。那么当我们继续判断子数组 A\[2:4]，我们只需要判断 A\[4]，同时结合 A\[2:3]的计数信息即可。**滑动窗口就是专门优化这种每次只在端点变化，中间都不变，从而省去了中间即重复计算，进而将窗口内的计数信息从 O(w) 降低到 O(1)**，其中 w 为窗口大小。
接下来，我们继续优化。实际上也是没有必要两层循环枚举所有子数组的。而是在 $O(n)$ 的时间就可以枚举所有的合法子数组。为什么呢？这是双指针的常见套路。其实你可以换个角度思考：
所有的子数组就是
* 以索引 0 为右端点的所有子数组
* 加上以索引 1 为右端点的所有子数组
* 加上以索引 2 为右端点的所有子数组
* ...
* 加上以索引 n - 1 为右端点的所有子数组，其中 n 为数组长度
这样的话我们就可以使用双指针技巧。右指针模拟右端点，使用左指针模拟左端点了。**如果以索引 i 为右端点的子数组 0 的个数不大于 k，那么左指针 l 没必要右移，因为当前右指针 r 和所有的索引 i, 其中 l <= i <= r 的组合 0 的个数都不会大于 k，但是子数组还更短了，不可能是答案，因此我们直接右移右指针，这是算法的关键**。通过这种方式算法的时间复杂度可从 $O(n^2)$ 降低到 $n$。
### 代码
* 语言支持：Python3
Python3 Code:
```py
class Solution:
def longestOnes(self, A: List[int], K: int) -> int:
i = ans = 0
for j in range(len(A)):
K -= A[j] == 0
while K < 0:
K += A[i] == 0
i += 1
ans = max(ans, j - i + 1)
return ans
```
甚至更简洁：
```py
class Solution:
def longestOnes(self, A: List[int], K: int) -> int:
i = 0
for j in range(len(A)):
K -= 1 - A[j]
if K < 0:
K += 1 - A[i]
i += 1
return j - i + 1
```
**复杂度分析**
令 n 为数组长度。
* 时间复杂度：$O(n)$
* 空间复杂度：$O(1)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1004.max-consecutive-ones-iii.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.