Pythonで合計がターゲット以上になる最短の部分リストのサイズを求めるプログラム

問題の概要

数値のリスト nums と整数 target が与えられます。このとき、要素の合計が target 以上となる最短の連続する部分リストのサイズを求めてください。条件を満たす部分リストが存在しない場合は -1 を返します。

たとえば、nums = [2, 11, -4, 17, 4]、target = 19 が入力された場合、出力は 2 になります。[17, 4] を選べば合計は 21 となり、19 以上という条件を満たすからです。

解法の考え方：累積和と単調キュー

この問題は、累積和（prefix sum）と単調キュー（monotonic deque）を組み合わせることで、O(n) の計算量で効率的に解くことができます。手順は以下の通りです。

• ps を要素 0 のみを持つリストとして初期化します。

• nums の各要素 num に対して次の処理を行います。

  • ps の末尾に「直前の累積値 + num」を追加し、累積和のリストを作成します。
  • もし num >= target であれば、その要素単体で条件を満たすため 1 を返します。

• min_size を無限大（inf）に、キュー q を [0] に、ポインタ j を 0 にそれぞれ初期化します。

• i を 1 から ps の長さまで順番に処理します。

  • j = min(j, len(q) - 1) でポインタをキューの範囲内に調整します。
  • ps[i] - ps[q[j]] >= target を満たしている間、min_size = min(min_size, i - q[j]) で最小サイズを更新し、j を 1 ずつ進めます。
  • キューが空でなく、かつ ps[i] <= ps[q[-1]] である間、キューの末尾を削除して単調性を維持します。
  • 現在のインデックス i をキューの末尾に追加します。

• 最後に、min_size が無限大より小さければその値を、そうでなければ -1 を返します。

なぜ単調キューが必要なのか？

リストに負の数が含まれている場合、単純な尺取り法（two pointers）では正しい答えが得られません。累積和が単調増加となるインデックスだけをキューに保持することで、「区間の始点として有望な候補」だけを効率的に管理できます。これにより、各インデックスは高々 1 回ずつ push / pop され、全体の計算量は O(n) に抑えられます。

Pythonでの実装例

以下が実際の実装コードです。

class Solution:
    def solve(self, nums, target):
        ps = [0]
        for num in nums:
             ps += [ps[-1] + num]
             if num >= target:
                 return 1
        min_size = float("inf")
        q = [0]
        j = 0
        for i in range(1, len(ps)):
             j = min(j, len(q) - 1)
             while j < len(q) and ps[i] - ps[q[j]] >= target:
                 min_size = min(min_size, i - q[j])
                 j += 1
             while q and ps[i] <= ps[q[-1]]:
                 q.pop()
             q.append(i)
        return min_size if min_size < float("inf") else -1

ob = Solution()
nums = [2, 11, -4, 17, 4]
target = 19
print(ob.solve(nums, target))

入力

[2, 11, -4, 17, 4], 19

出力

2

計算量の評価

• 時間計算量： O(n) — 各インデックスは最大 1 回ずつキューへの追加と削除が行われるためです。

• 空間計算量： O(n) — 累積和のリストとキューを保持するために必要です。