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

<https://leetcode-cn.com/problems/minimum-operations-to-reduce-x-to-zero>

## 题目描述

```
给你一个整数数组 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] <= 104
1 <= x <= 109
```

## 前置知识

* 堆
* [滑动窗口](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/slide-window)

## 公司

* 暂无

## 堆

### 思路

这里可以使用堆来解决。具体来说是我自己总结的**多路归并**题型。

> 关于这个算法套路，请期待后续的堆专题。

### 代码

代码支持：Python3

Python3 Code:

```python
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        # 看数据范围，这种方法铁定超时（指数复杂度）
        h = [(0, 0, len(nums) - 1, x)]
        while h:
            moves,l,r,remain = heapq.heappop(h)
            if remain == 0: return moves
            if l + 1 < len(nums): heapq.heappush(h, (moves + 1, l + 1,r, remain-nums[l]))
            if r > 0: heapq.heappush(h, (moves + 1, l,r-1, remain-nums[r]))
        return -1
```

**复杂度分析**

* 时间复杂度：$O(2^moves)$，其中 moves 为题目答案。最坏情况 moves 和 N 同阶，也就是 $2^N$。
* 空间复杂度：$O(1)$。

由于题目数组长度最大可以达到 10^5， 这提示我们此方法必然超时。

我们必须考虑时间复杂度更加优秀的方式。

## 动态规划（记忆化递归）

### 思路

由上面的解法， 我们不难想到使用动态规划来解决。

枚举所有的 l,r,x 组合，并找到最小的，其中 l 表示 左指针， r 表示右指针，x 表示剩余的数字。这里为了书写简单我使用了记忆化递归。

### 代码

代码支持：Python3

Python3 Code:

> Python 的 @lru\_cache 是缓存计算结果的数据结构， None 表示不限制容量。

```python
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        n = len(nums)

        @lru_cache(None)
        def dp(l, r, x):
            if x == 0:
                return 0
            if x < 0 or r < 0 or l > len(nums) - 1:
                return n + 1
            return 1 + min(dp(l + 1, r, x - nums[l]), dp(l, r - 1, x - nums[r]))

        ans = dp(0, len(nums) - 1, x)
        return -1 if ans > n else ans
```

**复杂度分析**

* 时间复杂度：$O(N^2 \* h)$，其中 N 为数组长度, h 为 x 的减少速度，最坏的情况可以达到三次方的复杂度。
* 空间复杂度：$O(N)$，其中 N 为数组长度，这里的空间指的是递归栈的开销。

这种复杂度仍然无法通过 10^5 规模，需要继续优化算法。

## 滑动窗口

### 思路

实际上，我们也可以逆向思考。即：我们剩下的数组一定是原数组的中间部分。

那是不是就是说，我们只要知道数据中子序和等于 sum(nums) - x 的长度。用 nums 的长度减去它就好了？

由于我们的目标是`最小操作数`，因此我们只要求**和为定值的最长子序列**，这是一个典型的[滑动窗口问题](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/thinkings/slide-window)。

### 代码

代码支持：Python3

Python3 Code:

```python
class Solution:
    def minOperations(self, nums: List[int], x: int) -> int:
        # 逆向求解，滑动窗口
        i = 0
        target = sum(nums) - x
        win = 0
        ans = len(nums)
        if target == 0: return ans
        for j in range(len(nums)):
            win += nums[j]
            while i < j and win > target:
                win -= nums[i]
                i += 1
            if win == target:
                ans = min(ans, len(nums) - (j - i + 1))
        return -1 if ans == len(nums) else ans
```

**复杂度分析**

* 时间复杂度：$O(N)$，其中 N 为数组长度。
* 空间复杂度：$O(1)$。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/1658.minimum-operations-to-reduce-x-to-zero.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.