用 Python 编写程序，查找将 X 归零的最少操作

pythonserver side programmingprogramming更新于 2025/11/30 5:32:17

假设我们有一个名为 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]。

为了解决这个问题，我们将遵循以下步骤 −

n := nums 的大小
leftMap := a new map
leftMap[0] := -1
left := 0
对于范围在 0 到 n - 1 内的 i，执行
- left := left + nums[i]
- 如果 left 不在 leftMap 中，则
  - leftMap[left] := i
right := 0
ans := n + 1
对于 i，范围从 n 到 0，减少 1，执行
- 如果 i < n，则
  - right := right + nums[i]
- left := x - right
- 如果 left 存在于 leftMap 中，则
  - ans := ans 和 leftMap[left] + 1 + n-i 的最小值
如果 ans 与 n + 1 相同，则
- 返回 -1
返回 ans

示例

让我们看看下面的实现以便更好地理解 −


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))