PythonでXをゼロに減らすための最小操作を見つけるプログラム

numsという配列と別の値xがあるとします。 1つの操作で、配列から左端または右端の要素を削除し、xから値を減算することができます。 xを正確に0に減らすために必要な操作の最小数を見つける必要があります。それが不可能な場合は、-1を返します。

したがって、入力がnums =[4,2,9,1,4,2,3] x =9のような場合、最初は左端の要素4を削除する必要があるため、出力は3になります。したがって、配列は次のようになります。 [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：=新しいマップ
• leftMap [0]：=-1
• 左：=0
• 0からn-1の範囲のiの場合、do
  • 左：=左+ nums [i]
  • leftがleftMapにない場合は、
    • leftMap [left]：=i
• 右：=0
• ans：=n + 1
• nから0の範囲のiの場合、1ずつ減らします。
  • i
  • right：=right + nums [i]
• 左：=x-右
• leftMapにleftが存在する場合、
  • ans：=最小のansとleftMap [left] + 1 + n-i

例

理解を深めるために、次の実装を見てみましょう-

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