Tìm các cặp có tổng cho trước trong danh sách liên kết đôi trong C++

Giới thiệu

Trong bài toán này, chúng ta được cho một danh sách liên kết đôi (doubly linked list) và một giá trị tổng (sum). Nhiệm vụ là tìm tất cả các cặp phần tử trong danh sách có tổng bằng giá trị cho trước.

Ví dụ minh họa

Đầu vào

head → 2 ↔ 5 ↔ 6 ↔ 9 ↔ 12, x = 11

Đầu ra

(2, 9), (5, 6)

Giải thích

• Cặp (2, 9): 2 + 9 = 11
• Cặp (5, 6): 5 + 6 = 11

Phương pháp 1: Duyệt lồng nhau (Brute Force)

Cách tiếp cận đơn giản là duyệt qua toàn bộ danh sách liên kết, lấy từng phần tử một và tìm phần tử còn lại trong danh sách sao cho tổng của hai phần tử bằng giá trị mục tiêu. Điều này được thực hiện bằng cách sử dụng hai vòng lặp lồng nhau.

Chương trình minh họa

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

Đầu ra

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

Phương pháp 2: Kỹ thuật hai con trỏ (Two Pointers) - Hiệu quả hơn

Tận dụng tính chất danh sách liên kết đã được sắp xếp, ta có thể sử dụng hai con trỏ: một trỏ về đầu (start) và một trỏ về cuối (end) của danh sách.

Thuật toán:

• Khởi tạo start trỏ đến head, end trỏ đến node cuối cùng.
• Tính sumVal = start->data + end->data.
• So sánh sumVal với sum:
  • Nếu sumVal > sum: dịch chuyển end sang trái (end = end->prev).
  • Nếu sumVal < sum: dịch chuyển start sang phải (start = start->next).
  • Nếu sumVal == sum: in cặp, dịch chuyển cả hai con trỏ (start = start->next, end = end->prev).
• Dừng khi hai con trỏ cắt nhau (start == end hoặc end->next == start).
• Đếm số cặp tìm thấy, nếu bằng 0 thì in "No Such Pairs found !".

Chương trình minh họa

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

Đầu ra

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

Độ phức tạp: Phương pháp 1 có độ phức tạp thời gian O(n²), phương pháp 2 chỉ O(n) nhờ danh sách đã sắp xếp.