C++에서 주어진 합계로 모든 쌍 인쇄

이 문제에서는 정수 배열과 정수 합이 주어지며 합이 합 값과 같은 모든 정수 쌍을 인쇄해야 합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 - 배열 ={1, 6, -2, 3} 합계 =4

출력 - (1, 3) , (6, -2)

여기에 주어진 합계 값과 쌍이 필요합니다.

문제에 대한 간단한 해결책은 합계를 생성하는 요소 쌍을 확인하는 것입니다. 이것은 배열을 순회하고 합계 값으로 합산되는 배열의 숫자를 찾아 수행할 수 있습니다.

예시

이 프로그램은 솔루션을 설명합니다 -

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

출력

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

이 방법은 이해하기 쉽지만 그다지 효율적이지 않습니다. 또 다른 방법은 해싱을 사용하는 것입니다.

해시 테이블을 초기화합니다. 배열을 탐색하고 배열에서 쌍을 찾습니다. 일치 시 배열을 인쇄합니다.

예시

다음 프로그램을 사용하면 알고리즘을 더 잘 이해할 수 있습니다. −

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

출력

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