Pythonで配列内の同一要素インデックスペア（i < j）を効率的にカウントする方法

問題概要

数値のリスト nums が与えられたとき、i < j を満たし、かつ nums[i] と nums[j] が等しいようなインデックスのペア (i, j) の個数を求めることを考えます。

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

解法のアプローチ

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

• Python標準ライブラリの Counter を使い、nums 内の各要素の出現回数を集計します。
• 変数 count を 0 に初期化します。
• 各要素の出現回数 n に対して、count に n × (n − 1) / 2 を加算します。
• 最終的な count を返します。

なぜ n × (n − 1) / 2 なのか？

ある値が n 回出現する場合、その中から2つのインデックスを選ぶ組み合わせの総数は、二項係数 C(n, 2) = n × (n − 1) / 2 で表されます。この公式を使うことで、各値ごとのペア数を一括して計算でき、全体的な計算量は O(N) に抑えられます。全ペアを素朴に二重ループで調べる O(N²) の方法よりも大幅に高速です。

実装例

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

from collections import Counter

def solve(nums):
   c = Counter(nums)
   count = 0
   for n in c.values():
      count += n * (n - 1) // 2
   return count

nums = [5, 4, 5, 4, 4]
print(solve(nums))

入力

[5, 4, 5, 4, 4]

出力

4