算法---滑动窗口练习-5（将x减到0的最小操作数）

1. 题目解析

题目地址：将x减到0的最小操作数

2. 讲解算法原理

算法的基本思想是使用双指针法来寻找满足条件的子数组。首先，计算数组nums的总和SUM，然后计算目标值target，即SUM - x。如果target小于0，说明无法通过删除操作得到目标值，直接返回-1。

接下来，使用两个指针left和right来维护一个滑动窗口，表示当前子数组的范围。初始时，两个指针都指向数组的第一个元素，窗口的初始和为0。

然后，不断移动右指针right，并将当前元素的值累加到sum中，直到sum大于target。此时，需要移动左指针left，并将左边界的元素从sum中减去，直到sum不大于target。在这个过程中，不断更新满足条件的子数组的最大长度len。

最后，返回结果len。如果len为-1，表示无法找到满足条件的子数组，返回-1；否则返回n - len，表示需要删除的元素个数。

---

3. 编写代码

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int left=0,right=0,n=nums.size();
        int len=-1,sum=0,target=0,SUM=0;
        for(int i=0;i<n;i++)
        SUM+=nums[i];
        target=SUM-x;
        if(target<0)
        return -1;
        while(right<n)
        {
            sum+=nums[right];//进窗口
            while(sum>target)//判断
            {
                sum-=nums[left++];//出窗口
            }
            if(sum==target)
            len=max(len,right-left+1);//更新
            right++;
        }

        return len==-1?-1:n-len;
    }
};
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