C++에서 a+b =c+d가 되도록 배열에서 4개의 요소 a, b, c 및 d를 찾습니다.

정수 목록이 있다고 가정합니다. 우리의 임무는 a+b =c+d가 되도록 (a, b) 및 (c, d)와 같은 두 쌍으로 4개의 고유한 정수를 찾는 것입니다. 답이 여러 개인 경우 하나만 인쇄하십시오. 배열 요소가 A =[7, 5, 9, 3, 6, 4, 2]와 같다고 가정하면 쌍은 (7, 3) 및 (6, 4)

여기서 우리는 해싱 기술을 사용할 것입니다. 해시 테이블의 값으로 쌍으로 합계를 키로 사용합니다. 이 문제를 해결하려면 다음 단계를 따라야 합니다.

• 0 ~ n – 1 범위의 i에 대해 다음을 수행합니다.
  • i + 1 ~ n – 1 범위의 j에 대해
    • 합계 구하기
    • 해시 테이블에 이미 합계가 있는 경우 이전 쌍과 현재 쌍을 인쇄합니다.
    • 그렇지 않으면 해시 테이블을 업데이트하십시오.

예시

#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)