Pythonで合計がターゲットと等しい重複しない部分配列の最大数を求めるプログラム

問題の概要

配列 nums と値 target が与えられたとします。このとき、各部分配列（サブ配列）の要素の合計が target と等しくなるような、空でない重複しない（オーバーラップしない）部分配列の最大数を求める必要があります。

例として、nums = [3,2,4,5,2,1,5]、target = 6 の場合を考えてみましょう。この場合の出力は 2 になります。これは、合計が 6 となる部分配列 [2,4] と [1,5] の2つが存在するためです。

解法のアプローチ

この問題は、累積和（プレフィックスサム）とセットを組み合わせることで、線形時間で効率的に解くことができます。手順は以下の通りです。

• t := 要素 0 のみを含む新しいセット
• temp := 0（現在位置までの累積和）
• ans := 0（答えのカウント）
• nums の各要素 i について以下を繰り返す：
  • temp := temp + i
  • prev := temp - target
  • prev が t に含まれる場合：
    • ans := ans + 1
    • t を要素 temp のみを含む新しいセットでリセット
  • それ以外の場合：
    • temp を t に追加
• ans を返す

なぜこの方法が機能するのか

ある位置での累積和から target を引いた値が、前回見つけた部分配列の終了位置以降に記録した累積和のセットの中に存在すれば、「その位置で終わる・合計が target に等しい新しい部分配列」が存在することを意味します。部分配列を見つけた時点でセットをリセットすることで、すでに採用した部分配列との重なりを防ぎ、常に非重複の条件を満たせるようになっています。また、最初に 0 をセットに入れておくことで、配列の先頭から始まる部分配列も正しく検出できます。

実装例

以下にPythonでの実装を示します。

def solve(nums, target):
    t = set([0])
    temp = 0
    ans = 0
    for i in nums:
        temp += i
        prev = temp - target
        if prev in t:
            ans += 1
            t = set([temp])
        else:
            t.add(temp)
    return ans

nums = [3,2,4,5,2,1,5]
target = 6
print(solve(nums, target))

入力

nums = [3,2,4,5,2,1,5], target = 6

出力

2

計算量の評価

配列を一度だけ走査し、セットへの挿入・参照は平均 O(1) で行えるため、時間計算量は O(n)、空間計算量も O(n) となります。非常に大きな入力に対しても高速に動作する効率的なアルゴリズムです。