Tìm bốn phần tử a, b, c và d trong một mảng sao cho a + b =c + d trong C ++

Giả sử chúng ta có một danh sách các số nguyên. Nhiệm vụ của chúng ta là tìm bốn số nguyên phân biệt thành hai cặp như (a, b) và (c, d), sao cho a + b =c + d. Nếu có nhiều câu trả lời, thì chỉ in một câu trả lời. Giả sử các phần tử của mảng là:A =[7, 5, 9, 3, 6, 4, 2], thì các cặp có thể là (7, 3) và (6, 4)

Ở đây chúng ta sẽ sử dụng kỹ thuật băm. Chúng tôi sử dụng tổng làm khóa dưới dạng cặp làm giá trị trong bảng băm. Chúng tôi phải làm theo các bước sau để giải quyết vấn đề này.

• Đối với tôi trong phạm vi từ 0 đến n - 1, hãy thực hiện
  • đối với j trong phạm vi i + 1 đến n - 1, thực hiện
    • tìm tổng số
    • Nếu bảng băm đã có tổng, hãy in cặp trước đó và cặp hiện tại
    • Nếu không, hãy cập nhật bảng băm.

Ví dụ

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

Đầu ra

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