Giả sử có một dãy n số. Chúng ta phải tìm ba số sao cho tổng của hai phần tử bằng số thứ ba. Vì vậy, nếu mảng giống như [5, 32, 1, 7, 10, 50, 19, 21, 2], đầu ra sẽ là 21, 2, 19. Nếu không tìm thấy phần tử nào như vậy, hãy hiển thị thông báo đó.
Để giải quyết vấn đề này, chúng ta sẽ làm theo một số bước như sau -
-
Sắp xếp mảng đã cho
-
Sau đó, bắt đầu sửa phần tử lớn nhất từ phần tử cuối cùng và duyệt qua mảng để tìm hai số khác tổng bằng phần tử thứ ba.
-
Lấy hai con trỏ j và k, j là từ đầu tiên, k là từ cuối cùng để tìm số nhỏ nhất trong hai số từ i - 1 để tìm số lớn nhất trong hai số còn lại.
-
Nếu phép cộng cả hai số vẫn nhỏ hơn Arr [i], thì chúng ta phải tăng giá trị của tổng của hai số, do đó tăng con trỏ j, để tăng giá trị của Arr [j] + Arr [ k]
-
Nếu phép cộng của cả hai số đều nhiều hơn Arr [i], thì chúng ta cần giảm giá trị của tổng của hai số, do đó giảm con trỏ k, sao cho giảm giá trị tổng thể của Arr [j] + Arr [k ]
Ví dụ
#include<iostream>
#include<algorithm>
#define N 5
using namespace std;
void getValueTriplet(int arr[], int n) {
sort(arr, arr + n);
for (int i = n - 1; i >= 0; i--) {
int j = 0;
int k = i - 1;
while (j < k) {
if (arr[i] == arr[j] + arr[k]) {
cout << "The numbers are " << arr[i] << " " << arr[j] << " " << arr[k] << endl;
return;
}
else if (arr[i] > arr[j] + arr[k])
j += 1;
else
k -= 1;
}
}
cout << "No such triplet exists";
}
int main() {
int arr[] = { 5, 32, 1, 7, 10, 50, 19, 21, 2 };
int n = sizeof(arr) / sizeof(arr[0]);
getValueTriplet(arr, n);
} Đầu ra
The numbers are 21 2 19