Pythonで配列を合計が等しい3つの部分に分割する方法

問題の概要

整数の配列 A が与えられたとき、その配列を合計が等しい3つの空でない部分に分割できる場合にのみ true を返す問題を考えます。

形式的には、i + 1 < j を満たすインデックス i, j が存在し、次の3つの区間の合計がすべて等しくなるとき、配列は分割可能とみなせます。

• 第1部分:A[0] + A[1] + ... + A[i]
• 第2部分:A[i+1] + A[i+2] + ... + A[j-1]
• 第3部分:A[j] + A[j+1] + ... + A[len(A)-1]

たとえば、入力が [0,2,1,-6,6,-7,9,1,2,0,1] の場合、出力は true になります。このとき配列は [0,2,1]、[-6,6,-7,9,1]、[2,0,1] の3つに分けられ、それぞれの合計はすべて 3 で一致します。

解法のアプローチ

この問題は、左右両方向からの累積和と2つのポインタを組み合わせることで効率的に解けます。手順は以下のとおりです。

• 全要素の合計 temp を求め、required_sum = temp / 3 を計算します。temp が3で割り切れない場合は、そもそも均等な3分割が不可能なので false を返します。
• 左から右へ走査しながら累積和 sum_left を作成します。
• 右から左へ走査しながら累積和 sum_right を作成します。
• index1 := 0、index2 := 配列の長さ − 1 として初期化します。
• index1 < index2 の間、次の処理を行います。
  • sum_left[index1] が required_sum と等しくなるまで index1 を右へ進めます。
  • sum_right[index2] が required_sum と等しくなるまで index2 を左へ戻します。
  • index1 < index2 かつ index1 ≠ index2 であれば true を返し、そうでなければ false を返します。

左右から同時に探索することで、中央の部分が必ず残る形になり、全体を1回の走査で判定できます。計算量は時間・空間ともに O(n) です。

実装例

以下はPythonでの実装例です。

class Solution(object):
    def canThreePartsEqualSum(self, A):
        temp = sum(A)
        # 合計が3で割り切れない場合は分割不可
        if temp % 3 != 0:
            return False

        n = len(A)
        # 左からの累積和
        sum_left = [0] * n
        sum_left[0] = A[0]
        # 右からの累積和
        sum_right = [0] * n
        sum_right[-1] = A[-1]

        for i in range(1, n):
            sum_left[i] = A[i] + sum_left[i - 1]
        for i in range(n - 2, -1, -1):
            sum_right[i] = A[i] + sum_right[i + 1]

        required_sum = temp / 3
        index1 = 0
        index2 = n - 1

        while index1 < index2:
            # 左側の境界候補を探す
            while index1 < index2 and sum_left[index1] != required_sum:
                index1 += 1
            # 右側の境界候補を探す
            while index2 > index1 and sum_right[index2] != required_sum:
                index2 -= 1
            return index1 < index2 and index1 != index2

ob1 = Solution()
print(ob1.canThreePartsEqualSum([0,2,2,-6,6,-7,9,2,2,0,2]))

入力

[0,2,1,-6,6,-7,9,1,2,0,1]

出力

true

このように、累積和を事前に計算しておくことで、各境界位置の判定を定数時間で行えるのがポイントです。負の数が含まれる配列でも正しく動作するため、実務的なデータにも応用しやすい手法といえます。