【优选算法 — 滑动窗口】最大连续1的个数 将 x 减到0的最小操作数

  

 

---

   最大连续1的个数  

---

  最大连续1的个数

---

   题目描述  

  题目解析  

1. 给我们一个元素全是0或者1的数组，和一个整数 k ，然后让我们在数组选出最多的 k 个0；
2. 这里翻转最多 k 个0的意思，是翻转 0 的个数<= k，而不是一定要翻转 k 个0； 
3. 然后把这 k 个0翻转成1，翻转完成后，找出数组中，连续1的最大个数。

---

 

  算法原理  

---

如果按照这个题，直接去把0翻转成1，我们会发现这个操作非常麻烦，因为如果后续还要枚举数组中别的0，就要先把刚刚翻转过的1翻转回0，代码也不好写；

通过上述两个例子，求最大连续1的个数的过程中，我们并没有真正地对0进行翻转，所以我们是可以不用翻转的；

我们只需要在数组中，找一段元素连续为0的区域，并且0的个数不超过k即可；

换而言之，只要这段区域的0的个数不超过k，那么就是一定可以成功翻转的，我们没必要真正地去翻转。

所以上述的问题可以转换成：找出最长子数组，0的个数不超过k个；

---

   解法一：暴力枚举 + zero计数器  

---

• 既然要找最长子数组，我们就固定一个起点，然后不断枚举所有0的个数不超过k的子数组；
• 并且返回所有子数组中，长度最大的子数组即可。

在暴力枚举的过程中，我们需要定义一个变量，来计数子数组中0的个数；

我们所有的优化方法，都是建立在暴力枚举的基础上，来做优化的，所以要考虑清楚暴力枚举的要点和细节，再在这些细节和要点上总结规律，并作出优化。

如果是暴力枚举的话，此时在 right 到达合适的位置后，left++，right = left，并且重复上面的过程;

但是我们可以发现，在后续的left 向后枚举的过程中，只要 left还在前面3个1的位置，right 能到达的最远位置是不变的；

 我们要对上述枚举的细节做优化。

---

  解法二：滑动窗口  

---

 

left 移动到能让 zero=2 的位置，此时只需要让 right 继续向后挪动

---

1. left = 0, right =0 ;
2. 进窗口 （right=1，无视；right = 0，zero++）；
3. 判段（zero > k） （3和4是循环）
4. 出窗口(left = 1，无视；left = 0，zero--)；
5. 更新结果

---

  编写代码  

  时间复杂度：

虽然有两层循环，但是根据实际过程，时间复杂度 O(N);

   空间复杂度：

只定义了有限的变量，所以是O(1) 

---

  将 x 减到0的最小操作数  

---

将 x 减到0的最小操作数

题目描述

---

  转换思路：找到数组中，长度最长，且和为 sum - x 的子数组  

---

如果我们直接按照题目的要求，每次操作都删除数组最左边，或者最右边的元素，使得 x=0，那么这道题的操作是非常麻烦的，因为能删除的方法非常多；

如果正面比较难，我们就使用“正难则反”的方法，这是非常重要的一点；

当我们计算数组两边的区间比较难找，我们可以转换思路，求中间的这一个连续的区间之和

 

• 我们只需要在数组中间找一段连续的区域，这段区域所有元素之和 target 等于 sum - x 即可；
• 题目要求的是最小操作数，所以是要找 左边区间 和 右边区间 的元素个数之和最小的情况即可；
• 进而转换为，在这个数组中，找到一块连续的区域，这个区域的所有元素之和，等于sum-x；
• 并且这个连续的区域是要最长的，长度设置为 len；
• 找到最长的 len，返回 length - len 即可

---

   解法：滑动窗口   

---

随机定义一个数组，来发现规律 

定义 sum1 变量，来标记 right 和 left 中间这段区域的和;

---

  在 right 向后遍历的时候:  

1. 当 sum1 > target 时，固定 right，移动 left
2. 当 sum1 = target 时，先更新 len，再移动 right，
3. 如果出现 sum1 >= target 的情况，按照上面的步骤处理

  证明 right 不需要往后移动：

此时 right 会停下，是因为刚刚好改变 sum1 和 target 的关系，再更新 len 之后，left++；

此时 left 在更新之后，left 和 right 中间的区域之和一定是小于 target 的，所以 right 不需要 --；

1. left = 0, right =0 ;
2. 进窗口(sum1 += num[right++]);
3. 判断sum1 > target（注意：sum = target 是我们要的结果，而判断是用来调整结果的，所以不写=)
4. 出窗口（sum1 -=nums[left++]）,3 和 4 是循环
5. 更新结果 （判断 sum1 是等于还是小于 target，==才更新结果）;

---

 编写代码 

上述情况是因为，在刚刚好遍历完成所有数组元素，sum1 才刚好等于 target 的，此时 len虽然还是0，但是只要最终结果返回 n - len ，依旧是正确答案；

但是也有在遍历完所有数组元素，sum1 都不能等于 target 的，所以要在返回结果时判断；

而上述示例二在执行到 return 时，刚好 len 也是0，但是要返回 -1；两种情况就刚好重合了；

---

  修改代码   

  ​​

​​