【优选算法】——滑动窗口—1658. 将 x 减到 0 的最小操作数

小李很执着

发布于 2024-06-15 09:58:51

1790

文章被收录于专栏：学习笔记学习笔记

1.题目

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

2. 解法（滑动窗⼝）：

算法思路：

题⽬要求的是数组「左端+右端」两段连续的、和为 x 的最短数组，信息量稍微多⼀些，不易理清思路；我们可以转化成求数组内⼀段连续的、和为 sum(nums) - x 的最⻓数组。此时，就是熟悉的「滑动窗⼝」问题了。

算法流程：

a. 转化问题：求target = sum(nums) - x 。如果 target < 0 ，问题⽆解； b. 初始化左右指针 left = 0 , right = 0 （滑动窗⼝区间表⽰为 [left, right) ，左右区间是否开闭很重要，必须设定与代码⼀致），记录当前滑动窗⼝内数组和的变量 sum = 0 ，记录当前满⾜条件数组的最⼤区间⻓度 maxLen = -1 ； c. 当 r ight⼩于等于数组⻓度时，⼀直循环：

如果 sum < target ，右移右指针，直⾄变量和⼤于等于 target ，或右指针已经移到头； ii. 如果 sum > target ，右移左指针，直⾄变量和⼩于等于 target ，或左指针已经移到头； iii. 如果经过前两步的左右移动使得 sum == target ，维护满⾜条件数组的最⼤⻓度，并让下个元素进⼊窗⼝； d. 循环结束后，如果 maxLen 的值有意义，则计算结果返回；否则，返回 -1 。

3.图解

4.代码实现

C语言

int minOperations(int* nums, int numsSize, int x) {
    int sum = 0;
    for (int i = 0; i < numsSize; i++)
        sum += nums[i];
    int target = sum - x;

    if (target < 0)
        return -1;

    int ret = -1;
    int left = 0, right = 0, tmp = 0;
    while (right < numsSize) {
        tmp += nums[right];      // 进窗口
        while (tmp > target)     // 判断
            tmp -= nums[left++]; // 出窗口
        if (tmp == target)       // 更新结果
            ret = ret > (right - left + 1) ? ret : (right - left + 1);
        right++;
    }

    if (ret == -1)
        return ret;
    else
        return numsSize - ret;
}

C++

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int sum = 0;
        for (int a : nums)
            sum += a;
        int target = sum - x;
        // 细节问题
        if (target < 0)
            return -1;
        int ret = -1;
        for (int left = 0, right = 0, tmp = 0; right < nums.size(); right++) {
            tmp += nums[right];      // 进窗⼝
            while (tmp > target)     // 判断
                tmp -= nums[left++]; // 出窗⼝
            if (tmp == target)       // 更新结果
                ret = max(ret, right - left + 1);
        }
        if (ret == -1)
            return ret;
        else
            return nums.size() - ret;
    }
};