Cho mảng số nguyên duy nhất và tổng S. Tìm tất cả bộ ba có tổng = S.
Input: array = {0, 2, -1, 1, -2} Sum = 1 Output: 1 2 -2; 0 2 -1
Cách 1: 3 vòng lặp O(n^3). Cách 2: Hashing - với mỗi i, dùng unordered_set tìm cặp (j, k) sao cho arr[j] + arr[k] = S - arr[i]. Cách 3: Sắp xếp mảng + 2 con trỏ (giảm không gian).
Chương trình minh họa (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 << "Các bộ ba có tổng 1:\n";
Triplets(arr, n, 1);
return 0;
}
Kết quả
0 2 -1 2 1 -2