L47.【LeetCode题解】1658. 将 x 减到 0 的最小操作数

zhangcoder

已于 2025-05-08 17:09:34 修改

阅读量767

点赞数 37

分类专栏： # 滑动窗口 LeetCode题解文章标签： leetcode 算法数据结构滑动窗口 c++ 开发语言

于 2025-05-08 08:42:37 首次发布

本文链接：https://blog.csdn.net/2401_85828611/article/details/147704537

版权

LeetCode题解同时被 2 个专栏收录

55 篇文章

订阅专栏

滑动窗口

6 篇文章

订阅专栏

1.题目

https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/

给你一个整数数组 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
示例 3：
输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
提示：

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^4
1 <= x <= 10^9

2.分析

例子分析

nums = [3,2,20,1,1,3], x = 10

3+2+1+1+3==10,移除红色区域的元素即可,红色区域一共5个数,绿色区域的元素被保留

算法分析

如果正向去分类讨论移除前几个和后几个元素讨论起来会非常麻烦,采用"正难则反"策略

不讨论移除红色区域的元素,而是讨论保留绿色区域的元素

由于题目要求"最小操作数",红色区域的元素个数要最小,则保留绿色区域的元素要最多

如果可以将x恰好减到0,则有下图:

则问题转化为:求一个子数组subnums,是否能满足子数组中所有的元素等于nums数组元素之和减去x,如果能满足返回最小操作数,如果不能,返回-1

和之前CC52.【C++ Cont】滑动窗口题解很像,按暴力解法优化后的滑动窗口算法做即可,设target==nums数组元素之和减去x

(注: nums数组元素之和使用范围for遍历累加即可)

循环变量为right,每循环一次就sum+=nums[right],如果sum>target,那么left右移,直到sum<=target停止右移,如果满足sum==target,执行len=max(len,right-left+1)即可,right到nums.size()-1时停止循环

从算法上看,时间复杂度为 $O(N)$ ,因为right只遍历一遍数组,而且求nums数组元素之和也只遍历一遍数组

代码

class Solution {
public:
    int minOperations(vector<int>& nums, int x)
    {
        int size = nums.size(), sum = 0, target=0, left = 0, right = 0, len = -1;
        for (auto a : nums)
            target += a;
        target -= x;
        if (target<0)
            return -1;
        for (;right<size;right++)
        {
            sum+=nums[right];
            while (sum>target)
                sum-=nums[left++];
            if (sum==target)
                len=max(len,right-left+1);
        }
        if (len==-1)
            return -1;
        else
            return size-len;
    }
};