พิมพ์ Triplets ทั้งหมดที่มีผลรวมกำหนดใน C++

ในปัญหานี้ เราจะได้รับ array ของจำนวนเต็มที่ไม่ซ้ำกันและผลรวม และต้องหา triplets ที่สามารถสร้างผลรวมเดียวกันได้

ตัวอย่างเพื่อแก้ปัญหา

Input: array = {0, 2, -1, 1, -2} Sum = 1
Output: 1 2 -2 0 2 -1

เพื่อแก้ปัญหานี้ เราจะหา triplets ทั้งหมดที่ให้ผลรวม วิธีง่ายคือใช้ 3 loops หาผลรวมขององค์ประกอบและคืน triplet ที่เหมาะสม

โปรแกรมตัวอย่าง (วิธีที่ 1 - Brute Force)

#include <iostream>
using namespace std;

void Triplets(int arr[], int n, int sum) {
    for (int i = 0; i < n - 2; i++) {
        for (int j = i + 1; j < n - 1; j++) {
            for (int k = j + 1; k < n; k++) {
                if (arr[i] + arr[j] + arr[k] == sum) {
                    cout << arr[i] << "\t" << arr[j] << "\t" << arr[k] << endl;
                }
            }
        }
    }
}

int main() {
    int arr[] = {0, 2, -1, 1, -2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The Triplets are : \n";
    Triplets(arr, n, 1);
    return 0;
}

ผลลัพธ์

The Triplets are -

0 2 -1
2 1 -2

แต่วิธีนี้ไม่มีประสิทธิภาพ เพราะ time complexity เป็น O(n³) จาก 3 loops ดังนั้นเราจะใช้เทคนิคอื่นเพื่อแก้ปัญหาอย่างมีประสิทธิภาพ

วิธีหนึ่งคือใช้ hashing ในวิธีนี้ เราจะหา pairs ของทุกองค์ประกอบที่เป็น complement ของกันและกัน เช่น สำหรับองค์ประกอบค่า x เราต้องการองค์ประกอบ -x

สิ่งนี้ลด time complexity ของโค้ดลง

โปรแกรมตัวอย่าง (วิธีที่ 2 - Hashing)

#include <bits/stdc++.h>
using namespace std;

void Triplets(int arr[], int n, int sum) {
    for (int i = 0; i < n - 1; i++) {
        unordered_set<int> triplet;
        for (int j = i + 1; j < n; j++) {
            int third = sum - (arr[i] + arr[j]);
            if (triplet.find(third) != triplet.end())
                cout << third << "\t" << arr[i] << "\t" << arr[j] << endl;
            else
                triplet.insert(arr[j]);
        }
    }
}

int main() {
    int arr[] = {0, 2, -1, 1, -2};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "The Triplets are : \n";
    Triplets(arr, n, 1);
    return 0;
}

ผลลัพธ์

The Triplets are -

0 2 -1
2 1 -2

วิธีนี้สามารถทำให้มีประสิทธิภาพมากขึ้นได้โดยการ sort array ซึ่งจะลด space complexity ของโค้ด