Pythonで配列から和がKになるペアを最大限取り除く方法を解説

問題の概要

nums という整数の配列と、もう一つの値 k が与えられます。1 回の操作では、合計が k に等しくなる 2 つの要素を nums から選び、それらを配列から取り除くことができます。ここでの課題は、この操作を実行できる最大回数を求めることです。

たとえば、入力が nums = [8,3,6,1,5]、k = 9 の場合、答えは 2 になります。これは、まず合計が 9 になる [3,6] を削除でき、その後同じく合計が 9 になる [8,1] も削除できるためです。残った要素は [5] だけとなり、これ以上操作は行えません。

解決のアプローチ

この問題は、各値の出現回数をカウントしながらペアを探していくことで効率的に解けます。手順は以下の通りです。

• まず、nums 内の各要素の出現頻度を保持するマップ(counter)を作成します。
• 結果を格納する変数 res を 0 で初期化します。
• counter 内の各値 num について、以下を判定します。
  • 補完値である k - num が counter 内に存在する場合:
    • num が k - num と異なる場合(例:num=3、k-num=6):両方のカウントのうち小さい方がペアとして成立するので、その最小値を res に加算し、両方のカウントを 0 にリセットします。
    • num が k - num と等しい場合(例:k=10、num=5):同じ値同士でペアを組むため、カウントを 2 で割った商がペアの数になります。
• 最終的に res を返します。

この方法なら、各要素を一度だけ走査すればよいため、時間計算量は O(n)、空間計算量も O(n) で済みます。

実装例

理解を深めるために、実際のコードを見てみましょう。

from collections import Counter

def solve(nums, k):
    counter = Counter(nums)
    res = 0
    for num in counter:
        if counter.get(k - num, 0):
            if num != k - num:
                res += min(counter[num], counter[k - num])
                counter[k - num] = 0
                counter[num] = 0
            else:
                res += int(counter[num] / 2)

    return res

nums = [8, 3, 6, 1, 5]
k = 9
print(solve(nums, k))

コードのポイント

collections.Counter を使うことで、配列内の各値の出現頻度を一行で取得できます。counter.get(k - num, 0) により、対応する補完値が存在しない場合でもエラーにならず安全に処理できます。また、ペアとして使用した値は必ずカウントを 0 にしているため、同じペアを二重に数えてしまう心配がありません。

入力例

[8, 3, 6, 1, 5], 9

出力例

2

このように、Counter を活用した頻度管理により、和が k になるペアの最大削除回数をシンプルかつ効率的に求めることができます。