专题二_滑动窗口_将x减到0的最小操作数
一：题目
解释：每次只能移除数组的边界，移除的边界的总和为x，要求返回你移除边界的最小操作数！
也就是说你最少花几次移除边界，就能够让这些移除的边界的和为x，则返回这个次数！
所以这个题目，肯定是要考虑三种情况
情况1：x为正数，小于整个数组之和，且有解决方案
例子：
输入：nums = [1,1,4,2,3], x = 5 输出：2 解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
情况2：x为正数，小于整个数组之和 ，但无解决方案！
输入：nums = [1,1,4,2,3], x = 8 输出：-1 解释：没有解决方案本质：x远大于数组的和
情况3：x为正数，但大于整个数组之和 ，所以无解决方案！
输入：nums = [1,1,4,2,3], x = 12 输出：-1 解释：没有解决方案 数组总和都才10本质：x远大于数组的和
注：x不可能为负数，题目已经规定了x>=1
二：算法
这道题，我们正向解题，是很难的，所以正难则反：
找"一段连续的区域和为sum - x"就可以了
而题目要求的是最小操作数，
所以找的是"最长的连续区域，且区域和为sum - x"
所以上面说过的三种情况，我们就可以进行区分了，假设sum - x的值，用tager来存储，则:
targe<0 代表符合情况3直接返回-1，反之则是情况1和情况2，则仍需要通过计算才可以得知是否存在解决方案
解释：
你只有x不大于数组之和，你是不可能一眼就能看出其有没有解决方案的，所以我们只能实现定义一个返回值，假设为ret，如果ret从始至终都没有被更新过，说明其没有解决方案，反之有解决方案！所以，情况3可以一开始就避免掉，但是情况2和情况1还需根据结果来判断！
①：暴力
O(N^2)，left以不同元素作为起点，right向右遍历，如果区间的和==targe，则记录，反之遍历完了都没有符合的，则left++，right从left位置开始向右遍历，继续判断....
注：保留的right肯定是从left开始遍历的，而不是left+1的位置，因为可能left下标的元素就==targe!
②：滑动窗口
暴力能优化的点：
1：left++后，我们的right不需要再回退到left处，而是就在原地！
解释：
left++是因为之前区间的和>targe了，所以更改起点left的位置来重新找，但是此时left++后，数组有三种情况：
a：数组之和仍大于targe，则right不需要懂，而left还需++
b：数组之和==targe，则判断更新结果之后，right再++
c：数组之和<targe，则right++
所以综上所述，right根本不需要回退到left处，只需要先保持不对，对区间的和判断之后，无非就是先left++，再right++或者直接right++罢了！
所以双指针同向移动，采用滑动窗口来解决即可！
三：代码
①：ret为操作数
class Solution {
public:int minOperations(vector<int>& nums, int x) {int ret=INT_MAX;//ret代表操作数 要返回最小的int targe=0;//查找区间的和int sum=0;//数组的总和for(auto a:nums) sum+=a;targe=sum-x;//计算出窗口的目标和 赋给targeif(targe<0) return -1;//对情况3 x大于整个数组和 进行特判for(int left=0,right=0,total=0;right<nums.size();right++){total+=nums[right];//进窗口while(total>targe)//区间不符合我们的要求{total-=nums[left++];//出窗口}if(total==targe)//符合我们的要求ret=min(ret,(n-(right-left+1)));//则判断更新ret 取最小操作数}return ret==INT_MAX?-1:ret;//有可能ret始终未更新 这就是情况2 反之就是情况1}
};易错：
①：情况3，x大于整个数组的情况，一定要在执行滑动窗口算法的之前进行特判，否则while循环中的total一定大于targe，这意味着不管你怎么出窗口，你的left会一直++，直到越界，会报错
②：ret代表的是最小操作数，所以博主一开始就取了INT_MAX，其次即使不是情况3，也有可能是情况2，所以ret可能从未被更新，仍为INT_MAX，所以若是为INT_MAX，则返回-1，返回代表情况1，直接返回ret就行
③：像left right toal，这种只需要在循环中用到的变量，直接在for循环定义就行，反之其他的变量，不能再for循环中定义
④：更新结果的前提一定是窗口区间的和total==targe，而不是直接更新
⑤：ret代表操作数，所以我们更新ret的时候，是数组总长度-窗口区间长度得到的
有些写法定义ret为符合要求的窗口区间的长度，所以在返回的时候，有一些变化
②：ret为区间长度
class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum = 0;for (auto a : nums) sum += a;int target = sum - x;// 情况3if (target < 0) return -1;int ret = -1; // 初始化结果为 -1（表示暂时无解）// 滑动窗口：寻找和为 target 的最长子数组for (int left = 0, right = 0, tmp = 0; right < nums.size(); right++) {tmp += nums[right]; // 进窗口while (tmp > target) // 窗口不符合要求tmp -= nums[left++]; // 出窗口if (tmp == target) // 判断更新ret = max(ret, right - left + 1); // 更新最大窗口长度}// 对情况2特判一下子if (ret == -1) return ret;else return nums.size() - ret;//ret是区间长度 所以操作数应该为总长度减去区间长度}
};解释：ret是区间长度，所以判断更新的时候轻松一点，但是最后返回的时候麻烦一点