ค้นหาคู่ที่มีผลรวมที่ระบุในรายการที่เชื่อมโยงเป็นสองเท่าใน C++

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

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

อินพุต

head − 2 <-> 5 <-> 6 <-> 9 <-> 12
x = 11

ผลลัพธ์

(2, 9), (5, 6)

คำอธิบาย

For pairs (2, 9), the sum of values is 11
For pairs (5, 6), the sum of values is 11

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

วิธีแก้ปัญหาอย่างง่ายคือการสำรวจรายการลิงก์ทั้งหมดและนำองค์ประกอบทีละรายการและค้นหาองค์ประกอบในรายการลิงก์ที่เหลือซึ่งผลรวมคือผลรวม ทำได้โดยใช้การวนซ้ำแบบซ้อน

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

ตัวอย่าง

#include<iostream>
using namespace std;
struct Node {
   int data;
   struct Node *next, *prev;
};
void findSumPairs(struct Node *head, int sum) {
   struct Node *first = head;
   int pairCount = 0;
   while (first != NULL) {
      struct Node *second = first -> next;
      while(second != NULL){
         if ((first->data + second->data) == sum) {
            pairCount++;
            cout<<"("<<first->data<<",
            "<<second->data<<")\n";
         }
         second = second -> next;
      }
      first = first -> next;
   }
   if (!pairCount)
      cout<<"No Such Pairs found !";
}
void insert(struct Node **head, int data) {
   struct Node *temp = new Node;
   temp->data = data;
   temp->next = temp->prev = NULL;
   if (!(*head))
      (*head) = temp;
   else{
      temp->next = *head;
      (*head)->prev = temp;
      (*head) = temp;
   }
}
int main() {
   struct Node *head = NULL;
   insert(&head, 12);
   insert(&head, 9);
   insert(&head, 6);
   insert(&head, 5);
   insert(&head, 2);
   int sum = 11;
   cout<<"Pair in the linked list with sum = "<<sum<<" :\n";
   findSumPairs(head, sum);
   return 0;
}

ผลลัพธ์

Pair in the linked list with sum = 11 :
(2, 9)
(5, 6)

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

ตอนนี้เราจะเพิ่มเพื่อค้นหา sumVal แล้วเปรียบเทียบกับ

given sum.
If sumVal > sum, move end pointer leftwards.
If sumVal < sum, move start pointer rightwards.
If sumVal == sum, print both values, move start pointer rightwards.

เมื่อพอยน์เตอร์ไขว้กันแตกออกจากลูป นอกจากนี้ เราจะนับจำนวนคู่ที่พบ หากมีค่าเท่ากับ 0 พิมพ์ว่า "ไม่พบคู่ดังกล่าว !"

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

ตัวอย่าง

#include<iostream>
using namespace std;
struct Node {
   int data;
   struct Node *next, *prev;
};
void findSumPairs(struct Node *head, int sum) {
   struct Node *start = head;
   struct Node *end = head;
   while (end->next != NULL)
      end = end->next;
   int pairCount = 0;
   while (start != NULL && end != NULL && start != end &&
   end->next != start) {
      if ((start->data + end->data) == sum) {
         pairCount++;
         cout<<"("<<start->data<<", "<<end->data<<")\n";
         start = start->next;
         end = end->prev;
      }
      else if ((start->data + end->data) < sum)
         start = start->next;
      else
         end = end->prev;
   }
   if (!pairCount)
      cout<<"No Such Pairs found !";
}
void insert(struct Node **head, int data) {
   struct Node *temp = new Node;
   temp->data = data;
   temp->next = temp->prev = NULL;
   if (!(*head))
      (*head) = temp;
   else{
      temp->next = *head;
      (*head)->prev = temp;
      (*head) = temp;
   }
}
int main() {
   struct Node *head = NULL;
   insert(&head, 12);
   insert(&head, 9);
   insert(&head, 6);
   insert(&head, 5);
   insert(&head, 2);
   int sum = 11;
   cout<<"Pair in the linked list with sum = "<<sum<<" :\n";
   findSumPairs(head, sum);
   return 0;
}

ผลลัพธ์

Pair in the linked list with sum = 11 :
(2, 9)
(5, 6)