【滑动窗口】将 x 减到 0 的最小操作数

利刃大大

发布于 2025-05-13 00:16:46

3600

代码可运行

文章被收录于专栏：csdn文章搬运csdn文章搬运

运行总次数：0

代码可运行

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

1658. 将 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 <= nums.length <= 105
1 <= nums[i] <= 104
1 <= x <= 109

解题思路：正难则反 + 滑动窗口

这道题如果我们直接去求两边的能减到零的组合的话，那是比较复杂的，但是如果我们换个思路，既然要求的是两边的操作数，那么我们正难则反，我们就去求中间那段区间，因为中间那段区间的要求，实际上是和两边区间的要求是相反的！

因为题目要求的是两边区间操作数的和就是要等于 x，那么中间区间的和不就是 sum - x 吗，对不对！其中 sum 就是整个数组的元素和。并且题目要求两边区间操作数的个数最少，那么只要我们中间区间的长度越大，那么两边的操作数不就越少，对不对！

总结一下就是，我们将题目转化为 求数组中间一段最长连续区间，该区间的元素和满足 sum - x。

那么既然是一段连续区间内求满足要求的最大长度，那岂不是可以用双指针的 ”滑动窗口“ 来解决！

对的！只不过要注意的是，我们进窗口的时机是 right 一直走就一直进窗口，而出窗口的条件是 tmp > target（参考下面代码中的变量名），而不是 tmp ≥ target，因为当 tmp == target 的时候是我们要更新最大长度的时候！

此外，最后返回的结果要用数组长度减去中间区间的长度，才是两边区间的长度！

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        // 先计算数组元素总和
        int sum = 0;
        for(auto e : nums)
            sum += e;

        int target = sum - x; // 这是我们窗口要求的目标和
        if(target < 0)  
            return -1; // 如果总和都小于x，那么直接不用干了

        int left = 0;
        int tmp = 0; // 记录窗口中元素的总和
        int maxlen = -1;
        for(int right = 0; right < nums.size(); ++right)
        {
            tmp += nums[right];
            while(tmp > target)
            {
                tmp -= nums[left++];
            }

            if(tmp == target)
                maxlen = max(minlen, right - left + 1);
        }
        return maxlen == -1 ? -1 : nums.size() - minlen;
    }
};