在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]。

要解决此问题，我们将遵循以下步骤−

n：= nums的大小
leftMap：=一个新的map
leftMap[0]：= -1
left：=0
for i在范围0到n-1中，执行以下操作
- left：= left + nums[i]
- 如果left不在leftMap中，则
  - leftMap[left]：= i
right：= 0
ans：= n+1
for 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))