Leetcode刷题详解——将x减到0的最小操作数

1. 题目链接：1658. 将 x 减到 0 的最小操作数

2. 题目描述:

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
1
2
3

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1
1
2

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
1
2
3

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104
• 1 <= x <= 109

3. 解法（滑动窗口）：

3.1 算法思路：

先计算出最长数组，用总长度减去减去最长数组，如果恰好减到0，返回最小操作数；否则返回-1

3.2 算法流程：

1. 转化问题：求target=sum-x。如果target<0,直接返回-1

2. 当right小于数组长度时，一直循环：

   • 如果tmp，右移右指针，直至变量和大于等于target，或右指针已经移到了头

   • 如果tmp>target，右移左指针，直至变量和大小等于target，或左指针已经移到了头

   • 如果经过前两步的左右移动使得tmp==target，维护满足条件数组的最大长度，并让下个元素进入窗口

   • 循环结束后，返回结果
     

class Solution {
public:
    int minOperations(vector& nums, int x) {
        int sum=0;
        int ret=-1;
        int left=0,right=0;
        int tmp=0;
        //计算所有元素的和
        for(int i=0;itarget)
            //窗口
            tmp-=nums[left++];
             //更新结果
            if(tmp==target)
            {
                ret=max(ret,right-left+1);
            }
            right++;
        }
        if(ret==-1)return ret;
        else return nums.size()-ret;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34