每日OJ题_算法_滑动窗口④_力扣1658. 将x减到0的最小操作数

目录

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

解析及代码

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

1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

难度 中等

给你一个整数数组?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 <= 10^5
• 1 <= nums[i] <= 10^4
• 1 <= x <= 10^9

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {

    }
};

解析及代码

转化成了最长子数组的长度，所有元素的和正好等于数组和 - x。

题意是从两边找几个数，使其的和等于x，从两边找的话很难，因为有时候删左边，有时候删右边，所以“正难则反”，可以找中间有没有等于数组和 - x的区间，这样两边的和就是x了。

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        // 时间O（N）， 空间O（1）
        int tmp = 0;
        for(auto& e : nums)
        {
            tmp += e;
        }
        int target = tmp - x;
        if(target < 0)
        {
            return -1;
        }

        int n = nums.size(), len = -1, sum = 0, left = 0, right = 0;
        while(right < n) // 找最大子数组的和，长度为len
        {
            sum += nums[right];
            while(sum > target) // 判断
            {
                sum -= nums[left++]; // 出窗口 然后left++
            }
            if(sum == target)
            {
                len = max(len, right - left + 1); // 更新结果
            }
            ++right; // 判断不符合了
        }
        return len == -1 ? len : (n - len);
    }
};