题目链接:1658. 将 x 减到 0 的最小操作数
这道题目的意思就是,给定一个整数数组,和一个x,只能从数组最左边或者最右边进行删除,使得x恰好等于0,并且要操作次数最少的情况,否则返回-1.
这道题直接进行删左右元素的话,有很多种情况,一下删左边一下删右边,同时还要保证,要最小操作次数。这样就有很多种情况,直接做非常复杂。
所以当正面做非常复杂的时候就考虑正难则反。
上图满足式子:sum = target +a+b,a+b = x。target = sum-x。
sum表示整个数组大小。target表示中间子数组大小。
既然我们要删除两边的数来保证x减去这些数为0,我们可以找中间的子数组数,使整个子数组和满足,整个数组和减去x的大小。然后再用整个数组长度减去子数组长度,就可以得到操作次数。但是要保证子数组长度最大,长度最大就可以保证操作次数最少。
这样就把找两边数转换成找中间子数组。找到中间最长子数组就相当于找到两边数。
就利用找最大字串方法,利用滑动窗口。
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int n = nums.size(),sum = 0;
int m = n-1;
while(m>=0) sum += nums[m--];
int target = sum - x;
int sum1 = 0;
int cut = -1;
if(target < 0) return -1;
for(int right = 0,left = 0;right<n;)
{
sum1 += nums[right];//进窗口
while(sum1 > target && left<n)//判断出窗口
{
left++;
sum1 -=nums[left-1];
}
if(sum1 == target)//更新
{
cut = max(cut,right-left+1);
}
right++;
}
if(cut == -1) return -1;
return n-cut;
}
};