2024年11月7日练习（滑动窗口算法）

一.1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

 1.题目描述：

这里来看一个例子，就能明白题目的意思了：

那么这里就是从数组左边和右边找值，然后让x减去刚刚找的值，最后能使x变成0，那么就可以找

到，并且题目要求找到最佳方案，那么就是操作最少的次数，就是减去数组里面最少的数。

这里可以方法2就是最优解，只操作了两次就使得变成了0，所以最后返回的结果就是2.

2.算法原理：

     这里从分析例子可以看出，这个题目如果硬解的话非常难，因为一会要删左边，一会要删右边

要有很多种情况要去考虑。既然按照题目的思路去想很难解出来的话，我们就换一种思维，正难则

反，我们就这样想：

题目的要求其实就是找到a+b=x，那么我们就不这样找，我们先给整个数组求和为sum，既然题目

要找a+b=x，那么中间那段连续的区域就等于sum-x。当我们找两边比较难找时，可以发现中间这

段是连续的，所以完全可以从中间下手。既然题目要求找到最小的操作数，其实转换一下就是要中

间这段区域最长。
 

那么问题就转换为：找出最长子数组的长度，且这段数组的元素和正好等于sum-x（target）。那

么操作数就等于整个数组的元素大小-最长子数组的长度。

这里我们就不管暴力解法了，因为前面解过找最长子数组的长度的题目，这里我们直接来看看是否

可以直接优化一下：

现在我们要做的事就是让right找到一个临界点使得left到right这段区间的和大于等于target：

当找到这个临界点后，right就没必要继续往后移动了，因为再往后移动他的和也是大于target：

其实我们可以发现到right前面这个元素到left的和一定是小于target的，因为加上right那个点值才是

大于target的。在暴力解法中我们找到这个临界的地方后，让left++，right回来，那么此时left没必

要回来，因为不管怎么样，这段区间的和始终小于target的，也是始终不用回来的，所以这里right

可以做优化一下，就是找到一个临界点的时候，就不用回来了。

这里left++后分为两种情况：

第一种就是right不动，left没++之前这段区间的和是大于target的，此时left++之后，正好加上

right此时这个点的值正好是目标值的话，right就不用动。

第二种就是right也++，因为left++之后，值变小了，之前如果恰好这段区间等于target

所以right又要++才能满足大于等于target。

既然说到这里，两个指针都是朝同一方向前进的，所以这里用滑动窗口算法来解决。

那么既然提到了滑动窗口，我们就left=0，right=0，然后进窗口，判断，出窗口，更新结果。

3.代码展示：

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sumarr=0;int n=nums.size();for(int i=0;i<n;i++){//求整个数组的和sumarr+=nums[i];}int target=sumarr-x;if(target<0) return -1;int ret=-1;for(int left=0,right=0,sum=0;right<n;right++){//进窗口：sum+=nums[right];while(sum>target)//判断{//出窗口sum-=nums[left];left++;} if(sum==target){ret=max(ret,right-left+1);}}if(ret==-1){return ret;}else{return n-ret;}}
};