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

Difficulty
Medium
Tags
滑动窗口
URL
https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/
Star
给你一个整数数组 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
通过次数12,540提交次数39,724

滑动窗口

思路
本题的窗口有些特殊，需要包括尾巴 或者头部。那么可以考虑 循环数组 ，然后得到满足条件的窗口后再判断，是否包括头部或者尾巴.
（法2更好）
题解
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        n = len(nums)
        wds =0
        l, r = 0, 0
        res = n+1
        while r < n * 2:
            wds += nums[r%n]
            r += 1
            while wds > x:
                wds -= nums[l%n]
                l += 1

            # 左边界 或者 右边界 必须在 数组边界上
            if wds == x and (l==0 or l <= n <= r):
                res = min(res, r-l)

        return res if res <= n else -1

滑动窗口

思路
题目让选择 和 为 x 的边上的最短数组。可以反向操作，选择中间 和 为 sum(nums)-x 的最长子数组，最后的答案就是 len(nums) - res.
题解
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        # 选择边上的 最少数字，使得其和为 x
        # 换个角度，选择中间的 最多数字，使得其和为 sum(nums) - x
        target = sum(nums)-x
        res = -1
        wds = 0
        l, r = 0, 0
        while r < len(nums):
            wds += nums[r]
            r += 1

            while l < r and wds > target:
                wds -= nums[l]
                l += 1
            
            if wds == target:
                res = max(res, r-l)

        
        return len(nums) - res if res != -1 else res