算法刷题:将 x 减到 0 的最小操作数

.

题目链接

将 x 减到 0 的最小操作数

题目详情

题目解析

正面做这道题比较难,我们可以进行逆向思维
将这道题理解为:
求数组中,最长的子数组,且子数组中的和为sum-x,其中sum为数组的总长度
那么问题就很简单了,接下来,我们利用滑动窗口来解决这个问题

滑动窗口

定义指针及其他变量

int left = 0,right = 0,//滑动窗口所需要的两个同向指针
n = nums.length,//数组的长度
ret = -1,//默认返回值,子数组的最大长度
strsum = 0;//子数组的和
int sum = 0;//数组的和
int tmp = sum-x;//子数组需要满足的和

进窗口

记录当前子数组的总和,即将strsum 加上right位置的值
strsum+=nums[right];

判断

判断当前子数组的总和是否大于子数组需要满足的和tmp

出窗口

如果strsum 大于tmp,则需要将子数组最左边的值移除子数组
strsum-=nums[left++];

更新结果

当strsum 等于tmp的时候,则需要更新子数组的最大长度,
ret = Math.max(ret,right-left+1);

我的答案

class Solution {public int minOperations(int[] nums, int x) {//将问题转化为,求最长字串,且字串的和为sum-x//求和int sum = 0;for(int a :nums){sum+=a;}int tmp = sum-x;if(tmp<0) return -1;//定义指针int left = 0,right = 0,n = nums.length,ret = -1,strsum = 0;for(;right<n;right++){//进窗口strsum+=nums[right];//判断while(strsum>tmp){//出窗口strsum-=nums[left++];}if(strsum==tmp){//更新结果ret = Math.max(ret,right-left+1);}}//返回结果return ret ==-1?-1:n-ret;}
}