Tìm các cặp trong mảng có tổng đã tồn tại trong mảng trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] gồm N số nguyên. Nhiệm vụ của chúng ta là tìm các cặp trong một mảng có các tổng đã tồn tại trong mảng. Chúng ta cần tìm các cặp có sum value =a value trong mảng

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào

arr[] = {1, 2, 4, 6, 7}

Đầu ra

(1, 6), (2, 4)

Giải thích

Đối với các cặp (1, 6), tổng các giá trị là 7 có trong mảng.

Đối với các cặp (2, 4), tổng các giá trị là 6 có trong mảng.

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản cho vấn đề là tìm tất cả các cặp có thể bằng cách sử dụng các phần tử của mảng. Sau đó tính tổng các giá trị của parir. Tìm kiếm giá trị tổng này trong mảng, in ra nếu có.

Ngoài ra, chúng tôi sẽ có một bộ đếm cho số lượng cặp. Và nếu nó là 0, chúng tôi sẽ in không tìm thấy cặp nào.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#include <iostream>
using namespace std;
void findSumPairsArr(int arr[], int n){
   int pairCount = 0;
   for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
         for (int k = 0; k < n; k++) {
            if (arr[i] + arr[j] == arr[k]) {
               cout<<"( "<<arr[i]<<", "<<arr[j]<<" ), sum = "<<(arr[i] + arr[j])<<"\n";
               pairCount++;
            }
         }
      }
   }
   if (!pairCount)
      cout<<"No Such Pairs found !";
}
int main() {
   int arr[] = { 1, 2, 4, 6, 7 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Pairs in array whose sum already exists in array : \n";
   findSumPairsArr(arr, n);
   return 0;
}

Đầu ra

Các cặp trong mảng có tổng đã tồn tại trong mảng -

( 1, 6 ), sum = 7
( 2, 4 ), sum = 6

Một cách tiếp cận khác hiệu quả hơn là giải quyết vấn đề bằng cách sử dụng bảng băm. Chúng tôi sẽ kiểm tra tất cả paris và sau đó tính tổng của chúng và kiểm tra xem nó có tồn tại trong mảng hay không và theo dõi nó. Nếu số lượng cặp là 0, hãy in "Không tìm thấy cặp nào như vậy!".

Ở đây, việc triển khai một bảng băm trong c được thực hiện bằng cách sử dụng unardered_set.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

#include <bits/stdc++.h>
using namespace std;
void findSumPairsArr(int arr[], int n) {
   unordered_set<int> HT;
   for (int i = 0; i < n; i++)
      HT.insert(arr[i]);
   int pairCount = 0;
   for (int i = 0; i < n; i++) {
      for (int j = i + 1; j < n; j++) {
         if (HT.find(arr[i] + arr[j]) != HT.end()) {
            cout<<"( "<<arr[i]<<", "<<arr[j]<<" ), sum =
            "<<(arr[i] + arr[j])<<"\n";
            pairCount ++;
         }
      }
   }
   if (!pairCount)
   cout<<"No Such Pairs found !";
}
int main() {
   int arr[] = {1, 2, 4, 6, 7 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Pairs in array whose sum already exists in array : \n";
   findSumPairsArr(arr, n);
   return 0;
}

Đầu ra

Các cặp trong mảng có tổng đã tồn tại trong mảng -

( 1, 6 ), sum = 7
( 2, 4 ), sum = 6