Pythonで合計が0となる最長の部分リストの長さを求める方法

問題概要

1と−1という2つの値だけを含むリストが与えられたとき、要素の合計が0になる最長の部分リスト（連続する部分列）の長さを求めます。

例えば、入力が nums = [1, 1, -1, 1, 1, -1, 1, -1, 1, -1] の場合、出力は 8 になります。これは、最長の部分リストが [-1, 1, 1, -1, 1, -1, 1, -1] であり、その合計が0だからです。

解法のアプローチ：累積和と辞書

この問題は「累積和（プレフィックスサム）」を使うことで効率的に解けます。ある位置 i までの累積和が cs であるとき、同じ累積和の値が以前に位置 j で現れていれば、区間 j+1 〜 i の合計は必ず0になります。そこで、各累積和が最初に出現したインデックスを辞書に記録しておき、同じ値が再び現れたときにその距離を計算するのがポイントです。

アルゴリズムの手順

• table := 新しい空の辞書（各累積和が最初に現れたインデックスを記録）
• cs := 0（現在の累積和）、max_diff := 0（答えとなる最大長）
• i を 0 から nums のサイズ − 1 まで繰り返す：
  
  • cs := cs + nums[i]
  • cs が 0 なら、先頭から i までの全体の合計が0なので、max_diff := max(i + 1, max_diff)
  • cs が table に存在するなら、max_diff := max(max_diff, i − table[cs])
  • そうでなければ、table[cs] := i
• max_diff を返す

実装例

class Solution:
    def solve(self, nums):
        table = {}
        cs = 0
        max_diff = 0
        for i in range(len(nums)):
            cs += nums[i]
            if cs == 0:
                max_diff = max(i + 1, max_diff)
            if cs in table:
                max_diff = max(max_diff, i - table[cs])
            else:
                table[cs] = i
        return max_diff

ob = Solution()
nums = [1, 1, -1, 1, 1, -1, 1, -1, 1, -1]
print(ob.solve(nums))

入力

[1, 1, -1, 1, 1, -1, 1, -1, 1, -1]

出力

8

動作の解説

このコードでは、リストを左から順に走査しながら累積和 cs を更新していきます。累積和が0になった時点で、先頭からの部分リスト全体の合計が0であることが分かります。また、同じ累積和が2回現れた場合は、その2つの位置の間にある要素の合計が必ず0になるため、その間隔が答えの候補となります。辞書には各累積和の最初の出現位置だけを保存するので、常に最大の長さを正しく求められます。

計算量

時間計算量は O(n)、空間計算量も O(n) です。すべての要素を一度だけ走査し、辞書への挿入・参照は平均 O(1) で行えるため、総当たり的な O(n²) の解法と比べて非常に効率的です。