C++でa+b =c + dとなるような配列で、4つの要素a、b、c、dを見つけます。

整数のリストがあるとします。私たちのタスクは、a + b =c + dとなるように、（a、b）と（c、d）のような2つのペアとして4つの異なる整数を見つけることです。複数の回答がある場合は、1つだけ印刷してください。配列要素が次のようであると仮定します：A =[7、5、9、3、6、4、2]の場合、ペアは（7、3）と（6、4）になります

ここでは、ハッシュ手法を使用します。合計をキーとして使用し、ペアとしてハッシュテーブルの値として使用します。この問題を解決するには、次の手順に従う必要があります。

• 0からn– 1の範囲のiについては、
  • i +1からn– 1の範囲のjの場合、do
    • 合計を見つける
    • ハッシュテーブルにすでに合計がある場合は、前のペアと現在のペアを出力します
    • それ以外の場合は、ハッシュテーブルを更新します。

例

#include<iostream>
#include<map>
using namespace std;
bool getTwoPairs(int arr[], int n) {
   map<int, pair<int, int> > hash_table;
   for (int i = 0; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
         int sum = arr[i] + arr[j];
         if (hash_table.find(sum) == hash_table.end())
            hash_table[sum] = make_pair(i, j);
         else {
            pair<int, int> pp = hash_table[sum];
            cout << "(" << arr[pp.first] << " + " << arr[pp.second] << ") = (" << arr[i] << " + " << arr[j] << ")";
            return true;
         }
      }
   }
   cout << "No pairs found";
   return false;
}
int main() {
   int arr[] = {7, 5, 9, 3, 6, 4, 2};
   int n = sizeof arr / sizeof arr[0];
   cout << "The pairs are: ";
   getTwoPairs(arr, n);
}

出力

The pairs are: (7 + 4) = (5 + 6)