C++で差がkに等しいすべての異なるペアを数える方法

はじめに

このチュートリアルでは、C++を使って「差がkに等しい異なるペア」を見つけて数える方法を解説します。

具体的には、整数型の配列と値kが与えられ、その中から差がちょうどkとなるすべての異なるペアを数えることが課題です。

アルゴリズムの考え方

最もシンプルなアプローチは、配列の要素を1つずつ順番に選び、それ以降の要素との差をすべてチェックする方法です。2つの要素の差がkに等しければ、カウンターを1つ増やします。

例えば、配列 {1, 5, 3, 4, 2}、k = 3 の場合、差が3となるペアは (1, 4) と (5, 2) の2つなので、答えは2になります。

実装例

#include<iostream>
using namespace std;

int count_diffK(int arr[], int n, int k) {
    int count = 0;
    // 要素を1つずつ選んで比較する
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++)
            if (arr[i] - arr[j] == k || arr[j] - arr[i] == k)
                count++;
    }
    return count;
}

int main() {
    int arr[] = {1, 5, 3, 4, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 3;
    cout << "Count of pairs with given diff is " << count_diffK(arr, n, k);
    return 0;
}

出力

Count of pairs with given diff is 2

計算量について

この方法では、すべての要素の組み合わせを比較するため、時間計算量は O(n²) となります。一方、追加のメモリは必要としないため、空間計算量は O(1) です。

配列のサイズが大きい場合は、配列をソートしてから二分探索や双方向ポインタを活用することで、O(n log n) まで計算量を抑える最適化も可能です。