Pythonでnums[i] = nums[j]となるペア（i, j）の個数を求めるプログラム

配列 nums が与えられたとき、nums[i] = nums[j] を満たし、かつ i ≠ j であるようなペア（i, j）の個数を求めることを考えます。

たとえば入力が nums = [1, 3, 1, 3, 5] の場合、出力は 4 になります。該当するペアは (0, 2)、(2, 0)、(1, 3)、(3, 1) の4つだからです。

解法のアプローチ

この問題は、各値の出現回数を集計してから組み合わせを計算することで、効率的に解くことができます。手順は以下の通りです。

• 出現回数を記録するための空の辞書（マップ）d を用意する
• nums の各要素 c について、すでに d に存在すればカウントを +1、なければ 1 を設定する
• 結果を格納する変数 res を 0 で初期化する
• 出現回数が 2 回以上の各値 c に対して、res += d[c] * (d[c] - 1) を加算する
• res を返す

ある値が n 回出現するとき、インデックスの異なる順序付きペアの数は n × (n − 1) 通りになります。これは「n 個から異なる2つを選んで並べる」場合の数 P(n, 2) に相当します。

実装例

以下のコードで実際の動作を確認してみましょう。

def solve(nums):
    d = {}
    for c in nums:
        d[c] = d[c] + 1 if c in d.keys() else 1

    res = 0
    for c in (x for x in d if d[x] > 1):
        res += (d[c] * (d[c] - 1))

    return res

nums = [1, 3, 1, 3, 5]
print(solve(nums))

入力

[1, 3, 1, 3, 5]

出力

4

計算量

このアルゴリズムは配列を一度走査してカウントし、その後辞書の要素を一度だけ走査するため、時間計算量は O(N)、追加で必要なメモリも O(N) です。全ペアを総当たりで調べる O(N²) の素朴な解法と比べて、大きな配列でも高速に処理できる点がメリットです。