พิมพ์คู่ทั้งหมดด้วยผลรวมที่กำหนดใน 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 ]