在 Python 中寻找将 X 减少到零的最小操作的程序

假设我们有一个名为 nums 的数组和另一个值 x。在一个操作中,我们可以从数组中删除最左边或最右边的元素,然后从 x 中减去该值。我们必须找到将 x 精确到 0 所需的最少操作次数。如果不可能,则返回 -1。

所以,如果输入像 nums = [4,2,9,1,4,2,3] x = 9,那么输出将是 3,因为首先我们必须删除最左边的元素 4,所以数组将是[2,9,1,4,2,3] 和 x 将是 5,然后删除最右边的元素 3,所以数组将是 [2,9,1,4,2],并且 x = 2,然后再次要么从左或从右使 x = 0,数组将是 [2,9,1,4] 或 [9,1,4,2]。

示例

让我们看看以下实现以获得更好的理解 -

def solve(nums, x):
   n = len(nums)

   leftMap = dict()
   leftMap[0] = -1
   left = 0
   for i in range(n):
      left += nums[i]
      if left not in leftMap:
         leftMap[left] = i

   right = 0
   ans = n + 1
   for i in range(n, -1, -1):
      if i < n:
         right += nums[i]
      left = x - right
      if left in leftMap:
         ans = min(ans, leftMap[left] + 1 + n - i)
   if ans == n + 1:
      return -1
   return ans

nums = [4,2,9,1,4,2,3]
x = 9
print(solve(nums, x))

输入

[4,2,9,1,4,2,3], 9
输出结果
3