ค้นหาคู่ในอาร์เรย์ที่มีผลรวมอยู่แล้วในอาร์เรย์ใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ซึ่งประกอบด้วยจำนวนเต็ม N งานของเราคือการหาคู่ในอาร์เรย์ที่มีผลรวมอยู่แล้วในอาร์เรย์ เราต้องหาคู่ที่มีค่าผลรวม =ค่าในอาร์เรย์

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

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

ผลลัพธ์

(1, 6), (2, 4)

คำอธิบาย

สำหรับคู่ (1, 6) ผลรวมของค่าคือ 7 ซึ่งมีอยู่ในอาร์เรย์

สำหรับคู่ (2, 4) ผลรวมของค่าคือ 6 ซึ่งมีอยู่ในอาร์เรย์

แนวทางการแก้ปัญหา

วิธีแก้ปัญหาอย่างง่ายคือการค้นหาคู่ทั้งหมดที่เป็นไปได้โดยใช้องค์ประกอบของอาร์เรย์ จากนั้นคำนวณผลรวมของค่า parir ค้นหาค่าผลรวมนี้ในอาร์เรย์ พิมพ์ถ้ามี

นอกจากนี้เรายังจะมีตัวนับจำนวนคู่ และถ้าเป็น 0 เราจะพิมพ์ว่าไม่พบคู่ใด

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

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

ผลลัพธ์

จับคู่ในอาร์เรย์ที่มีผลรวมอยู่แล้วในอาร์เรย์ -

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

อีกวิธีหนึ่งที่มีประสิทธิภาพมากกว่าคือการแก้ปัญหาโดยใช้ตารางแฮช เราจะตรวจสอบปารีสทั้งหมดแล้วคำนวณผลรวมและตรวจสอบว่ามีอยู่ในอาร์เรย์หรือไม่และติดตาม หาก pairCount เป็น 0 ให้พิมพ์ "No such Pairs found !".

ที่นี่ การนำตารางแฮชไปใช้ใน c ทำได้โดยใช้ unordered_set

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

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

ผลลัพธ์

จับคู่ในอาร์เรย์ที่มีผลรวมอยู่แล้วในอาร์เรย์ -

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