思路:
题目要求是让我们从数组的最左端和最右端进行操作,这样的话解题的难度大大提升,我们可以用 正难则反 的思想:
- 题目中要求是减去数组中的数刚好等于X,我们可以转换成 数组中某一段的和等于 数组的总长减去X(sum - X)
- 然后题目要求求出最小的操作数,也就是最小的长度,转换成求数组中某一段的和等于 数组的总长减去X(target = sum - X)这个数组的最大长度,然后再用总长减去这个
解法一:还是暴力遍历,过程就不描述了,
然后解法二是在暴力遍历的基础上进行优化,用同向双指针
解法二:滑动窗口(同向双指针)
- 定义left、right在起始位置,然后固定left,让right向后遍历,把遍历的值加起来
- 当和大于target的时候,让和减去left所在位置的值,然后left也向后移动
- 当和等于target的时候,更新最大长度
- 当一值都没有更新的时候,说明不能恰好减到0,就返回-1,(len初始长度就设置为-1)
代码:
public int minOperations(int[] nums, int x) {
int sum1 = 0;
for(int i = 0; i < nums.length; i++){
sum1 += nums[i];
}
int len = -1;
int target = sum1 - x;
if(target < 0){
return -1;
}
for(int left = 0,right = 0,sum = 0; right < nums.length; right++){
//进窗口
sum += nums[right];
while(sum > target){
//出窗口
sum -= nums[left++];
}
//更新结果
if(sum == target){
len = Math.max(len,right - left + 1);
}
}
if(len == -1){
return -1;
}else{
return nums.length - len;
}
}