【Python】配列の両端から要素を削除してXをちょうど0にする最小操作回数を求めるアルゴリズム

問題の概要

数値の配列 nums と値 x が与えられます。1回の操作では、配列の左端または右端の要素を1つ削除し、その値を x から差し引きます。x をちょうど 0 にするために必要な最小の操作回数を求めてください。どうしても達成できない場合は -1 を返します。

入力例と動作の流れ

たとえば、nums = [4,2,9,1,4,2,3]、x = 9 が入力された場合、出力は 3 になります。具体的な手順は次のとおりです。

1. まず左端の要素 4 を削除 → 配列は [2,9,1,4,2,3] となり、x は 5 になります。
2. 次に右端の要素 3 を削除 → 配列は [2,9,1,4,2] となり、x は 2 になります。
3. 最後に左端の 2(右端も同じく 2)を削除 → x が 0 になり、配列は [2,9,1,4] または [9,1,4,2] となります。

解法のアプローチ

この問題を解くには、以下の手順に従います。

• n := nums のサイズ
• leftMap := 新しいマップ(辞書)
• leftMap[0] := -1(まだ何も削除していない状態を表す)
• left := 0
• i を 0 から n−1 まで繰り返す:
  • left := left + nums[i]
  • left が leftMap に存在しない場合は、leftMap[left] := i
• right := 0、ans := n + 1
• i を n から 0 まで 1 ずつ減らしながら繰り返す:
  • i < n の場合は、right := right + nums[i]
  • left := x - right
  • left が leftMap に存在する場合は、ans := min(ans, leftMap[left] + 1 + n - i)
• ans が n + 1 と等しい場合は、-1 を返す
• それ以外の場合は、ans を返す

なぜこの方法が効率的なのか

このアプローチのポイントは、「左端から削除した要素の合計」と「右端から削除した要素の合計」を組み合わせて x と一致させる分割を見つけることにあります。左側からの累積和をあらかじめハッシュマップに記録しておけば、右側からの累積和を計算しながら、残りに必要な値(x − 右側の合計)が左側に存在するかどうかを O(1) で判定できます。これにより、全体の計算量は O(n) に抑えられます。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

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

このように、累積和とハッシュマップを組み合わせることで、両端からの削除操作を効率的にシミュレートでき、線形時間で最小操作回数を求めることができます。