Pythonで解く「Kプレフィックス」問題：累積和を使って最大インデックスを効率的に求める方法

問題の概要

数値のリスト nums と整数 k が与えられたとき、「nums[0] + nums[1] + ... + nums[i] ≤ k」という条件を満たす最大のインデックス i を求めるのがこの問題です。条件を満たす i がひとつも存在しない場合は、-1 を返します。

たとえば、nums = [4, -7, 5, 2, 6]、k = 5 という入力の場合、答えは 3 になります。これは、先頭から nums[3] までを足すと 4 + (-7) + 5 + 2 = 4 となり、k 以下だからです。しかし最後の要素まで加えると合計が k を超えてしまうため、有効な最大インデックスは 3 ということになります。

解法のアプローチ：累積和（Prefix Sum）を活用する

この問題は「累積和」を使うことでシンプルに解決できます。手順は以下の通りです。

• ステップ1： インデックス 1 から順に、各要素へ直前の要素を加算していき、元のリストをそのまま累積和の配列に変換します。
  • nums[i] := nums[i] + nums[i-1]
• ステップ2： 変換後の配列を末尾から先頭へ向かって走査します。nums[i] ≤ k を満たす最初のインデックスが見つかった時点で、それが答えなので即座に返します。
• ステップ3： 最後まで条件を満たす要素が存在しなければ、-1 を返します。

リストには負の数も含まれる可能性があるため、累積和は単調増加とは限りません。そのため二分探索などは使えず、末尾から順に確認することで確実に「最大のインデックス」を見つけられるのがこの手法のポイントです。

実装例

以下は Python による具体的な実装です。

class Solution:
    def solve(self, nums, k):
        # 累積和を作成
        for i in range(1, len(nums)):
            nums[i] += nums[i-1]
        # 後ろから条件を満たす最大のインデックスを探す
        for i in range(len(nums)-1, -1, -1):
            if nums[i] <= k:
                return i
        return -1

ob = Solution()
nums = [4, -7, 5, 2, 6]
k = 5
print(ob.solve(nums, k))

入力

[4, -7, 5, 2, 6], 5

出力

3

計算量の評価

累積和の構築に O(n)、後方からの走査にも O(n) しかかからないため、全体の時間計算量は O(n) です。また、入力リストをそのまま再利用しているため、追加のメモリ消費は O(1) で済みます。シンプルながら非常に効率的な解法と言えます。