题目:

解答:

逆向思维。弹出的数之和等于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)

Logo

开源鸿蒙跨平台开发社区汇聚开发者与厂商,共建“一次开发,多端部署”的开源生态,致力于降低跨端开发门槛,推动万物智联创新。

更多推荐