Pythonを使用して、それぞれがターゲット合計を持つ2つの重複しないサブ配列を見つけるプログラム

arrの配列と別の値のターゲットがあるとします。それぞれがターゲットに等しい合計を持つarrの2つの重複しないサブ配列を見つける必要があります。複数の回答がある場合は、2つのサブ配列の長さの合計が最小になる回答を見つける必要があります。必要な2つのサブ配列の長さの最小合計を見つける必要があります。そのようなサブ配列がない場合は、-1を返します。

したがって、入力がarr =[5,2,6,3,2,5] target =5のような場合、出力は2になります。合計5の3つのサブ配列があり、それらは[5]、[3,2]です。 ]と[5]、現在は2つだけが最小サイズです。

これを解決するには、次の手順に従います-

• ans：=無限大

• best：=arrと同じサイズの配列を作成し、無限大で埋める

• プレフィックス：=0

• 最新：=キー0に-1を格納するマップ

• arrの各インデックスiと値xについて、実行します

  • プレフィックス：=プレフィックス+ x

  • （prefix --target）が最新のものである場合、

    • ii：=最新[プレフィックス-ターゲット]

    • ii> =0の場合、

      • ans：=ansの最小値と（i --ii + best [ii]）

    • best [i]：=i --ii

  • iがゼロ以外の場合、

    • 最新[プレフィックス]：=i

• ans <999999の場合はansを返し、それ以外の場合は-1

  を返します。

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

例

def solve(arr, target):
   ans = 999999
   best = [999999]*len(arr)
   prefix = 0
   latest = {0: -1}
   for i, x in enumerate(arr):
      prefix += x
      if prefix - target in latest:
         ii = latest[prefix - target]
         if ii >= 0:
            ans = min(ans, i - ii + best[ii])
         best[i] = i - ii
      if i: best[i] = min(best[i-1], best[i])
      latest[prefix] = i
   return ans if ans < 999999 else -1
arr = [5,2,6,3,2,5]
target = 5
print(solve(arr, target))

入力

[5,2,6,3,2,5], 5

出力

2