滑动窗口算法深度解析：LeetCode 经典例题实战

12. 将 x 减到 0 的最小操作数

题目链接

题目描述：

给你一个整数数组 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，最优的操作次数是 2 次。对于示例 2，不论是从左边还是右边进行删除操作，x 永远不可能到 0，所以返回 -1。

我们将问题进行转换：原来要求的是从最左边或者最右边进行删除元素，直到 x 变成 0。我们可以将问题区域划分，左边的区域是 a，右边的区域是 b，a 区域和 b 区域里面的数值加起来等于 x。那么中间剩下的就是我们整个数组的值减去 x。题目让我们求出最小的操作次数，也就是说 a+b 最短的情况，换种思路，就是中间区域最长的情况，即 sum-x。我们只要求出整个数组中和为 sum-x 的区域的最长值就行了。

找出最长的子数组的长度，子数组的所有元素的和正好等于 sum-x。

做这种题我们可以想对立面。我们可以先想想暴力解法：设置两个指针，左和右，一开始指向起点，让右指针进行移动操作，直到两个指针的区域间的值大于等于 sum-x，我们就更新下我们的操作次数，然后移动左指针继续进行更新的操作。

当左指针往右边移动了，右指针就没有必要往左边进行移动了，因为左指针向右移动过后，区间中的元素大小更小了，右指针只能往右移动。

在这个暴力解法的基础上进行优化：

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for (int a : nums) {
            sum += a;
        }
        int target = sum - x;
        // 细节问题，target 的值不能小于 0
        if (target < 0) return -1;
        int ret = -1;
        for (int left = , right = , tmp = ; right < nums.(); right++) {
            
            tmp += nums[right]; 
             (tmp > target) { 
                tmp -= nums[left];
                left++; 
            }
             (tmp == target) { 
                
                ret = (ret, right - left + );
            }
        }
         (ret == )  ret; 
          nums.() - ret; 
    }
};