C++で解く：配列とkが与えられたときの|ai + aj − k|の最小値とペアの個数を求める方法

問題文

n個の整数からなる配列と整数Kが与えられます。i ≠ j を満たす順序を区別しないペア {i, j} のうち、|ai + aj − k| の絶対値が最小となるようなペアの総数を求めてください。

例

例として、arr[ ] = {0, 4, 6, 2, 4}、k = 7 の場合を考えてみましょう。このとき最小値は 1 となり、以下の5つのペアが条件を満たします。

{0, 6}, {4, 2}, {4, 4}, {6, 2}, {2, 4}

アルゴリズム

考え方はシンプルで、すべてのペアを列挙し、各ペアについて abs(ai + aj − K) の値が現在の最小値より小さいかどうかを確認します。判定結果に応じて、以下の3つの場合に分けて処理を行います。

• abs(ai + aj − K) > 最小値 の場合：このペアは最小値に寄与しないため、何もしません。
• abs(ai + aj − K) = 最小値 の場合：最小値となるペアの個数を1つ増やします。
• abs(ai + aj − K) < 最小値 の場合：最小値を更新し、ペアの個数を1にリセットします。

この方法では二重ループですべてのペアを調べるため、計算量は O(n²) となります。配列のサイズがそれほど大きくない場合には十分実用的なアプローチです。

実装例

以下にC++での実装例を示します。

#include <iostream>
#include <climits>
#include <cmath>
using namespace std;

void getPairs(int *arr, int n, int k) {
    int minValue = INT_MAX;
    int pairs = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            int val = abs(arr[i] + arr[j] - k);
            if (val < minValue) {
                minValue = val;
                pairs = 1;
            } else if (val == minValue) {
                ++pairs;
            }
        }
    }
    cout << "Min value = " << minValue << endl;
    cout << "Total pairs = " << pairs << endl;
}

int main() {
    int arr[] = {0, 4, 6, 2, 4};
    int k = 7;
    int n = sizeof(arr) / sizeof(arr[0]);
    getPairs(arr, n, k);
    return 0;
}

出力

上記のプログラムをコンパイルして実行すると、以下の出力が得られます。

Min value = 1
Total pairs = 5

まとめ

この問題は、全ペアを走査しながら最小値とその出現回数を管理することで解くことができます。最小値が更新されたタイミングでカウントをリセットし、同じ最小値が現れたらカウントを増やす、というシンプルなロジックがポイントです。より大きな入力に対しては、ソートやハッシュマップを活用した最適化も検討できますが、まずはこの全探索によるアプローチを理解しておくことが重要です。