1658. 将 x 减到 0 的最小操作数
·
题目:

解答:
逆向思维。弹出的数之和等于x,那么剩下的数之和也能确定。维护窗口[left,right],窗口左右就是弹出的数,那么只需要保证窗口内的数大小等于target=(所有数总和-x)。
right遍历数组,sum存储窗口内的总和,每次遍历sum加入right对应的值,当sum大于target时弹出左边数直到小于等于,等于时更新ans,小于则继续遍历right。
最后还需要判断ans是否小于0,小于0说明无论如何都不能满足,return -1即可。否则说明存在满足的情况,ans保存的是窗口内数组的长度,那么就return len-ans。
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int len = nums.size();
int target = reduce(nums.begin(),nums.end())-x;
if(target<0) return -1;
int left=0,right=0;
int sum = 0;
int ans = -1;
for(right;right<len;right++){
sum+=nums[right];
while(sum>target){
sum-=nums[left];
left++;
}
if(sum==target)
ans = max(ans,right-left+1);
}
return ans<0?-1:len-ans;
}
};
时间复杂度O(n)
空间复杂度O(1)
更多推荐


所有评论(0)