Trong bài toán này, chúng ta đưa ra một mảng các số nguyên duy nhất và một tổng. Và chúng ta phải tìm ra bộ ba có thể tạo thành samesum.
Hãy lấy một ví dụ để giải quyết vấn đề -
Input : array = {0 , 2 , -1 , 1, -2}
Sum = 1
Output : 1 2 -2
0 2 -1 Để giải quyết vấn đề này, chúng ta sẽ tìm tất cả các bộ ba cung cấp tổng. Một cách tiếp cận đơn giản sẽ là sử dụng ba vòng lặp và tìm tổng các phần tử và trả về bộ ba thích hợp.
Ví dụ
#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;
}
}
}
}
}
// Driver code
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;
} Đầu ra
Bộ ba là -
0 2 -1 2 1 -2
Nhưng cách tiếp cận này không hiệu quả vì nó sẽ có độ phức tạp về thời gian là o (n 3 ) để chạy ba vòng. Vì vậy, chúng tôi sẽ sử dụng các kỹ thuật khác để giải quyết vấn đề này một cách hiệu quả.
Một phương pháp là sử dụng băm. Trong phương pháp này, chúng tôi sẽ tìm các cặp của mọi phần tử sao cho chúng bổ sung cho nhau, tức là đối với phần tử có giá trị x, chúng tôi cần một phần tử -x.
Điều này làm giảm độ phức tạp về thời gian của mã.
Ví dụ
#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;
} Đầu ra
Bộ ba là -
0 2 -1 2 1 -2
Phương pháp này có thể được thực hiện hiệu quả hơn bằng cách sắp xếp mảng sẽ làm giảm độ phức tạp về không gian của mã.