滑动窗同向双指针-将x减到0的最操作数
目录
滑动窗⼝（同向双指针）—将x减到0的最⼩操作数
给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
示例 1：
输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
示例 2：
输入：nums = [5,6,7,8,9], x = 4
输出：-1
问题分析
可以转化成 求数组内⼀段连续的、和为 sum(nums) - x 的最⻓数组 。此时，就是熟悉的「滑动窗⼝」问题了
代码解决
class Solution {
public int minOperations(int[] nums, int x) {
int s = 0;
for(int a=0;a<nums.length;a++){
s+=nums[a];
}
int sum = 0;
int ret = -1;
int target = s-x;
if(target < 0) {
return -1;
}
for(int left =0,right=0;right<nums.length; right++){
sum += nums[right];//进窗口
while(sum>target){//判断
sum -= nums[left++];
}
if(sum==target){
ret = Math.max(ret,right-left+1);//更新结果
}
}
if(ret == -1) return ret;
else return nums.length - ret;
}
}执行用时
