Pythonで配列内に「他の全要素の合計と等しい値」の要素が存在するか判定する方法

nums という名前の配列が与えられたとき、その配列の中に「残りのすべての要素の合計と等しい値を持つ要素」が存在するかどうかを判定する問題を考えてみましょう。

例えば、入力が nums = [3,2,10,4,1] の場合、10 = (3 + 2 + 4 + 1) となるため、出力は True になります。

解法のポイント

ある要素が他の要素の合計と等しいとき、その要素は必ず配列全体の合計の半分(total ÷ 2)になります。したがって、以下の手順で効率的に判定できます。

• freq := 要素の出現回数を記録する空の辞書(マップ)を用意
• total := 配列の合計値を格納する変数を 0 で初期化
• i を 0 から nums のサイズ - 1 まで繰り返す:
  • freq[nums[i]] のカウントを 1 増やす
  • total に nums[i] を加算
• total が偶数の場合:
  • freq[total // 2](total の半分の値)の出現回数が 0 でなければ、True を返す
• それ以外は False を返す

この方法なら、配列を一度走査するだけで判定できるため、時間計算量は O(n) と非常に効率的です。

それでは、実際の実装例を見て理解を深めましょう。

サンプルコード

from collections import defaultdict
def solve(nums):
    freq = defaultdict(int)

    total = 0
    for i in range(len(nums)):
        freq[nums[i]] += 1
        total += nums[i]
        
    if total % 2 == 0:
        if freq[total // 2]:
            return True
    return False
 
nums = [3,2,10,4,1]
print(solve(nums))

入力

[3,2,10,4,1]

出力

True

コードの解説

このコードでは、defaultdict(int) を使うことで、まだ存在しないキーにアクセスしても自動的に 0 で初期化されるため、出現回数のカウント処理がシンプルになります。まずループで各要素の出現回数と合計値を求め、その後「合計が偶数であること」と「合計の半分の値が配列内に存在すること」の2つの条件を確認しています。

なお、合計が奇数の場合は半分の値が整数にならないため、条件を満たす要素は存在しないことになり、即座に False を返せばよい点にも注目してください。