Pythonで配列内の「良いペア」の数を数えるプログラム

問題の概要

整数の配列 nums が与えられたとします。ここで、ペア (i, j) は nums[i] と nums[j] の値が等しく、かつ i < j を満たすときに「良いペア（good pair）」と定義されます。この記事では、配列の中に良いペアがいくつ存在するかを数える方法を解説します。

例えば、入力が nums = [5,6,7,5,5,7] の場合、出力は 4 になります。これは、インデックスの組み合わせ (0, 3)、(0, 4)、(3, 4)、(2, 5) の4つが条件を満たすためです。

解き方の手順

基本的なアプローチは、すべてのペアの組み合わせを調べて条件に一致するものをカウントすることです。手順は以下の通りです。

• カウンター変数 count を 0 で初期化します。
• 配列のサイズを n として取得します。
• 外側のループで i を 0 から n-1 まで動かします。
• 内側のループで j を i+1 から n-1 まで動かします。
• nums[i] == nums[j] が成り立つ場合は count を 1 増やします。
• 最後に count を返します。

Pythonでの実装例

実際のコードを見てみましょう。

def solve(nums):
    count = 0
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] == nums[j]:
                count += 1
    return count

nums = [5, 6, 7, 5, 5, 7]
print(solve(nums))

入力と出力

入力：

[5, 6, 7, 5, 5, 7]

出力：

4

計算量について

この二重ループによる解法の時間計算量は O(n²) です。配列のサイズが小さいうちは問題ありませんが、要素数が数千〜数万になると処理が遅くなる点に注意が必要です。

より効率的な解法：Counterを使う方法

数学的な性質を利用すると、計算量を O(n) まで削減できます。ある値が配列内に k 回出現するとき、その値から作れるペアの数は組み合わせの公式 k × (k − 1) / 2 で求められます。

from collections import Counter

def solve(nums):
    counter = Counter(nums)
    return sum(v * (v - 1) // 2 for v in counter.values())

nums = [5, 6, 7, 5, 5, 7]
print(solve(nums))  # 出力: 4

この方法では各値の出現回数を一度だけ数えればよいため、大きなデータセットでも高速に動作します。用途やデータ規模に応じて、両方のアプローチを使い分けるとよいでしょう。