Links

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 <= 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)$。