1.题目
题目分析:
题目给出整数数组和整数x,整数x表示操作数值,可以移除数组的左右俩边一个数,每移除一次,x 就要减去移除数字的大小,如果x变为0就返回移除的次数,不等于0就返回-1.
2.算法原理
正面来处理是复杂的,不知道左右那边来进行移除,就可以从反面来处理,要求最小操作数,就可以求最大的长度,因为操作数就是移除了多个元素,移除最小,则处理后的数组就是最大的,那求出最大的数组就可以反向得到最小的操作数了。就可以用窗口滑动来解决。
注意:target=数组元素和-x,因为整数数组没有负数,所以target就要大于0,不然就返回-1.
3.代码实现
class Solution {
public:int minOperations(vector<int>& nums, int x) {int target = accumulate(nums.begin(),nums.end(),0)-x;if(target<0)return -1;int n=nums.size();int sum1=0;int operation=INT_MIN;for(int left=0,right=0;right<n;right++){sum1+=nums[right];while(sum1>target){sum1-=nums[left++];}if(sum1==target)operation=max(operation,right-left+1);}return operation==INT_MIN?-1:n-operation;}};