Pythonで差がkに等しいすべてのペアを検索する方法

この記事では、リスト内の数値の中から、差がちょうど k に等しいペアの個数を数える方法を解説します。対象となる数値はリスト形式で与えられ、プログラムには値 k を引数として渡します。ここでは、for ループを使う方法とwhile ループを使う方法の2つのアプローチを紹介します。

for ループを使う方法

このアプローチでは、二重の for ループを使用します。外側の for ループでリストの各要素を順番に走査し、内側の for ループで残りの要素と外側の要素を比較します。両者の差が要求された値 k と一致した場合、カウント用の変数 count を1つずつ増やしていきます。

サンプルコード

listA = [5, 3, 7, 2, 9]

k = 2
count = 0

# リストの各要素を走査
for i in range(0, len(listA)):

    # 残りの要素とペアを作成して比較
    for j in range(i + 1, len(listA)):

        if listA[i] - listA[j] == k or listA[j] - listA[i] == k:
            count += 1

print("Required Pairs: ", count)

実行結果

上記のコードを実行すると、次の結果が得られます。

Required Pairs: 3

この例では、(5, 3)、(5, 7)、(9, 7) の3組が差 2 を満たすため、結果は 3 となります。

while ループを使う方法

もう一つのアプローチとして、while ループと if-else 文を組み合わせる方法があります。まずリストをあらかじめソートしておき、2つのインデックス（current_index と next_index）を使って要素同士の差を調べます。差が k より大きい場合は next_index を、小さい場合は current_index を進めることで、無駄な比較を減らしながら効率的にペアを探索できます。

サンプルコード

listA = [5, 3, 7, 2, 9]

k = 2
count = 0

# リストをソート
listA.sort()

next_index = 0
current_index = 0

while current_index < len(listA):
    if listA[current_index] - listA[next_index] == k:
        count += 1
        next_index += 1
        current_index += 1

    elif listA[current_index] - listA[next_index] > k:
        next_index += 1
    else:
        current_index += 1

print("Required Pairs: ", count)

実行結果

上記のコードを実行すると、次の結果が得られます。

Required Pairs: 3

計算量の違い

二重の for ループを使う方法は、すべての要素の組み合わせを調べるため、時間計算量は O(n²) になります。一方、while ループを使う方法は、ソートに O(n log n) かかるものの、その後の探索は2つのインデックスを一度だけ進めていくため、全体でも O(n log n) で済みます。データ件数が多い場合は、後者のアプローチの方が高速に動作します。