Pythonで合計がターゲットに一致する重複しない2つの部分配列を見つけるプログラム

問題の概要

配列 arr と整数 target が与えられたとします。ここで、arr の中から互いに重なり合わない2つの部分配列を見つけ、それぞれの要素の合計が target と一致するようにします。条件を満たす組み合わせが複数存在する場合は、2つの部分配列の長さの合計が最小になるものを選択します。求める答えはその長さの合計の最小値であり、該当する部分配列が存在しない場合は -1 を返します。

例として、入力が arr = [5,2,6,3,2,5]、target = 5 の場合を考えてみましょう。合計が 5 になる部分配列には [5]、[3,2]、[5] の3つがあります。この中から重ならない2つを選び、長さの合計を最小にすると、長さ1の [5] と [5] の組み合わせが最適となり、答えは 2 になります。

アルゴリズムのアプローチ

この問題は、累積和（プレフィックスサム）とハッシュマップを組み合わせることで効率的に解けます。「あるインデックスまでに見つかった target に一致する部分配列の最短の長さ」を記録しておくことで、現在の部分配列と重ならない過去の候補を素早く参照できるのがポイントです。

• ans := 無限大（答えの初期値）

• best := arr と同じサイズの配列を作り、すべて無限大で初期化する

• prefix := 0（累積和）

• latest := キー 0 に対して -1 を格納したマップ

• arr の各インデックス i と値 x について以下を実行する

  • prefix := prefix + x

  • (prefix - target) が latest に存在する場合

    • ii := latest[prefix - target]

    • ii >= 0 であれば

      • ans := ans と (i - ii + best[ii]) の最小値

    • best[i] := i - ii

  • i が 0 以外の場合

    • latest[prefix] := i

• ans < 999999 であれば ans を返し、それ以外は -1 を返す

実装例

以下のPythonコードで実際の動作を確認できます。

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

コードのポイント

このアルゴリズムの計算量は O(n) です。latest マップは「ある累積和が最後に現れたインデックス」を記録し、best 配列は「インデックス i までに見つかった target に一致する部分配列の最短の長さ」を保持します。これにより、現在見つけた部分配列の終端 i と、それより前に終わる別の部分配列を組み合わせた場合の総長を即座に評価でき、配列を一度走査するだけで答えを求められます。