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을 찾기 위해 then을 추가한 다음

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과 같으면 "No 그러한 쌍을 찾을 수 없습니다!"를 인쇄하십시오.

우리 솔루션의 작동을 설명하는 프로그램

예시

#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)