In tất cả các cặp có tổng cho trước trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng các số nguyên và một tổng số nguyên và chúng ta phải in ra tất cả các cặp số nguyên có tổng bằng giá trị tổng.

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

Đầu vào - mảng ={1, 6, -2, 3} sum =4

Đầu ra - (1, 3), (6, -2)

Ở đây, chúng ta cần các cặp có giá trị tổng đã cho.

Một giải pháp đơn giản cho vấn đề sẽ là kiểm tra các cặp phần tử tạo ra tổng. Điều này có thể được thực hiện bằng cách duyệt qua mảng và tìm số trong mảng có tổng giá trị tổng.

Ví dụ

Chương trình này sẽ minh họa giải pháp -

#include <iostream>
using namespace std;
int printPairsWithSum(int arr[], int n, int sum){
   int count = 0;
   for (int i = 0; i < n; i++)
      for (int j = i + 1; j < n; j++)
         if (arr[i] + arr[j] == sum)
            cout<<"[ "<<arr[i]<<", "<<arr[j]<<" ]\n";
}
int main(){
   int arr[] = {1, 6, -2, 3};
   int n = 4;
   int sum = 4;
   cout<<"Pairs with Sum "<<sum<<" are :\n";
   printPairsWithSum(arr, n, sum);
   return 0;
}

Đầu ra

Pairs with Sum 4 are :
[ 1, 3 ]
[ 6, -2 ]

Phương pháp này dễ hiểu nhưng không hoàn toàn hiệu quả. Một cách khác sẽ là sử dụng hàm băm.

Chúng tôi sẽ khởi chạy bảng băm và duyệt qua mảng và tìm các cặp trong đó. Khi khớp, chúng tôi sẽ in mảng:

Ví dụ

Chương trình sau sẽ giúp bạn hiểu rõ hơn về thuật toán -

#include <bits/stdc++.h>
using namespace std;
void printPairsWithSum(int arr[], int n, int sum){
   unordered_map<int, int> pair;
   for (int i = 0; i < n; i++) {
      int rem = sum - arr[i];
      if (pair.find(rem) != pair.end()) {
         int count = pair[rem];
         for (int j = 0; j < count; j++)
         cout<<"["<<rem<<", "<<arr[i]<<" ]\n";
      }
      pair[arr[i]]++;
   }
}
int main(){
   int arr[] = {1, 6, -2, 3};
   int n = 4;
   int sum = 4;
   cout<<"The pair with sum is \n";
   printPairsWithSum(arr, n, sum);
   return 0;
}

Đầu ra

Pairs with Sum 4 are :
[ 1, 3 ]
[ 6, -2 ]