521，滑动窗口解最大连续1的个数 III
There is no pressure when you are making a dream come true.
当你是在为梦想成真努力时，就不会有压力。
问题描述
给定一个由若干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的最长连续子数组，并且我们还有魔法，可以把K个0变为1。这题使用滑动窗口解决应该是最容易理解的。
我们可以使用两个指针，一个指向窗口的左边，一个指向窗口的右边，每次遍历数组的时候窗口左边的指针先不动，窗口右边的指针始终都会往右移动，然后顺便统计窗口内0的个数，如果0的个数大于K的时候，说明我们即使使用魔法，也不能把窗口内的所有数字都变为1，这个时候我们在移动窗口左边的指针，直到窗口内0的个数不大于K为止……，具体可以参照下图
来看下代码
1public int longestOnes(int[] A, int K) {
2 int left = 0;//窗口左边的位置
3 int maxWindow = 0;//窗口的最大值
4 int zeroCount = 0;//窗口中0的个数
5 for (int right = 0; right < A.length; right++) {
6 if (A[right] == 0) {
7 zeroCount++;
8 }
9 //如果窗口中0的个数超过了K，要缩小窗口的大小，直到0的个数
10 //不大于K位置
11 while (zeroCount > K) {
12 if (A[left++] == 0)
13 zeroCount--;
14 }
15 //记录最大的窗口
16 maxWindow = Math.max(maxWindow, right - left + 1);
17 }
18 return maxWindow;
19}
其实还可以换种思路，当窗口内0的个数刚好大于K的时候（也就是zeroCount+1==K），说明这个时候right指向的肯定是0，那么目前为止最大的窗口大小是(right-1)-left，因为窗口的右指针是一直往右滑动的，我们可以通过改变左指针的位置来缩小窗口。
所以right-left(注意这里的left已经执行++了，在下面的第10行)始终指向的是最大窗口的值，最后我们只需要返回right-left即可，不需要while循环，来看下代码
1public int longestOnes(int[] A, int K) {
2 int left = 0;//窗口左边的位置
3 int right = 0;//窗口右边的位置
4 int zeroCount = 0;//窗口中0的个数
5 for (; right < A.length; right++) {
6 if (A[right] == 0) {
7 zeroCount++;
8 }
9 //如果窗口中0的个数超过了K，要缩小窗口的大小
10 if (zeroCount > K && A[left++] == 0)
11 zeroCount--;
12 }
13 return right - left;
14}
或者还可以更简洁一些，其实原理都一样，换汤不换药。
1public int longestOnes(int[] A, int K) {
2 int left = 0;//窗口左边的位置
3 int right = 0;//窗口右边的位置
4 int zeroCount = 0;//窗口中0的个数
5 for (; right < A.length; right++) {
6 zeroCount += 1 - A[right];
7 if (zeroCount > K)
8 zeroCount -= 1 - A[left++];
9 }
10 return right - left;
11}
总结
滑动窗口和回溯算法其实都有一个经典的模板，对于回溯算法可以看下450，什么叫回溯算法，一看就会，一写就废。而滑动窗口问题，首先要使用两个指针，一个确定窗口的左边界，一个确定窗口的右边界，其中左边界不动，右边界往右移动，每移动一步都要判断窗口内的值是否满足条件，如果满足，要记录下最优值。如果不满足，左边界在开始移动，相当于缩小窗口……。滑动窗口的题有很多，有时间再对滑动窗口做个总结。
截止到目前我已经写了500多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有800多页，大家可以在公众号中回复关键字“pdf”即可获取下载链接。