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
- 堆
- 滑动窗口
- 暂无
这里可以使用堆来解决。具体来说是我自己总结的多路归并题型。
关于这个算法套路，请期待后续的堆专题。
代码支持：Python3
Python3 Code:
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 表示不限制容量。
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 的长度减去它就好了？
由于我们的目标是最小操作数，因此我们只要求和为定值的最长子序列，这是一个典型的滑动窗口问题。
代码支持：Python3
Python3 Code:
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)$。