【优选算法必刷100题】第011~012题（同向双指针：滑动窗口算法）：最大连续1的个数 III、将 x 减到 0 的最小操作数
🔥艾莉丝努力练剑：个人主页
❄专栏传送门：《C语言》、《数据结构与算法》、C/C++干货分享&学习过程记录、Linux操作系统编程详解、笔试/面试常见算法：从基础到进阶
⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平
🎬艾莉丝的简介：
🎬艾莉丝的算法专栏简介：
目录
011 最大连续1的个数 III
力扣链接：1004. 最大连续1的个数 III
力扣题解链接：滑动窗口解决【最大连续1的个数III】问题
题目描述：
1.1 题目详解
1.2 算法原理以及代码实现
1.2.1 解法思路：滑动窗口
不要去想怎么翻转，不要把问题想的很复杂，这道题的结果无非就是一段连续的1中间塞了k个0。
因此，我们可以把问题转化成：求数组中一段最长的连续区间，要求这段区间内的个数不超过k个。
既然是连续区间，可以考虑使用「滑动窗口」来解决问题。
1.2.2 算法流程
1、初始化一个大小为2的数组就可以当做哈希表（hash）了；初始化一些变量left = 0，right =0，ret = 0；
2、当right小于数组大小的时候，一直下列循环——
（1）让当前元素进入窗口，顺便统计到哈希表中；
（2）检查 0 的个数是否超标：
1）如果超标，依次让左侧元素滑出窗口，顺便更新哈希表的值，直到的个数恢复正
常；
（3）程序到这里，说明窗口内元素是符合要求的，更新结果；
（4）right++，处理下一个元素；
3、循环结束后，ret存的就是最终结果。
1.2.3 代码实现
class Solution { public: int longestOnes(vector<int>& nums, int k) { int ret = 0; for (int left = 0, right = 0, zero = 0; right < nums.size(); right++) { // 进窗口 if (nums[right] == 0) zero++; // 判断 while (zero > k) if (nums[left++] == 0) zero--; // 出窗口 // 更新结果 ret = max(ret, right - left + 1); } return ret; } };时间复杂度：O(n)，空间复杂度：O(1)。
1.3 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己推导很重要！
012 将 x 减到 0 的最小操作数
力扣题解链接：滑动窗口解决【将 x 减到 0 的最小操作数】问题
题目描述：
2.1 题目详解
2.2 算法原理
2.2.1 解法思路：滑动窗口
题目要求的是数组「左端+右端」两段连续的、和为x的最短数组，信息量稍微多一些，不易理清思路；我们可以转化成求数组内一段连续的、和为sum(nums) - x的最长数组。此时，就是熟悉的「滑动窗口」问题了。
这道题和我们介绍【滑动窗口】的第一道题目LCR 008. 长度最小的子数组有点像。
相关博客链接：【优选算法必刷100题】第009~010题（同向双指针：滑动窗口算法）：长度最小的子数组、无重复字符的最长子串问题求解
2.2.2 算法流程
1、转化问题：求target = sum(nums) - x。如果target＜0，问题无解;
2、初始化左右指针 l = 0，r = 0（滑动窗口区间表示为 [ l，r) ，左右区间是否开闭很重要，必须设定与代码一致），记录当前滑动窗口内数组和的变量sum=◎，记录当前满足条件数组的最大区间长度maxLen = -1；
3、当小于等于数组长度时，一直循环：
（1）如果sum<target，右移右指针，直至变量和大于等于target，或右指针已经移到头；
（2）如果sum>target，右移左指针，直至变量和小于等于target，或左指针已经移到头；
（3）如果经过前两步的左右移动使得sum == target，维护满足条件数组的最大长度，并
让下个元素进入窗口。
4、循环结束后，如果maxLen的值有意义，则计算结果返回；否则，返回 -1。
2.2.3 代码实现
class Solution { public: int minOperations(vector<int>& nums, int x) { int sum = 0; for (int a : nums)sum += a; int target = sum - x; //细节问题 if (target < 0)return -1; int ret = -1; for (int left = 0, right = 0, tmp = 0; right < nums.size(); right++)//tmp：和sum区分 { tmp += nums[right];//进窗口 //判断 while (tmp > target) tmp -= nums[left++];//出窗口 if (tmp == target)//更新结果 ret = max(ret, right - left + 1); } if (ret == -1)return ret; else return nums.size() - ret; } };时间复杂度：O(n)，空间复杂度：O(1)。
2.3 博主手记
本题整个的思路、算法原理、解题过程博主在纸上推导了一遍，大家可以参考一下手记的推导过程！最好做题的过程中自己也推导一遍！！！自己推导很重要！
结尾
往期回顾：
【优选算法必刷100题】第009~010题（同向双指针：滑动窗口算法）：长度最小的子数组、无重复字符的最长子串问题求解
结语：看到这里，不要忘记给博主来个“一键四连”哦！
🗡博主在这里放了一只小狗，大家看完了摸摸小狗放松一下吧！🗡
૮₍ ˶ ˊ ᴥ ˋ˶₎ა
