In tất cả bộ ba (triplet) tạo thành cấp số cộng trong mảng đã sắp xếp C++

Cho mảng đã sắp xếp, tìm tất cả bộ ba (i, j, k) tạo thành cấp số cộng (AP).

Cấp số cộng: Hiệu giữa 2 số liên tiếp bằng nhau.

Input: {2, 5, 7, 8, 9, 10} Output: 2 5 8; 5 7 9; 7 8 9; 8 9 10

Cách đơn giản: 3 vòng lặp O(n^3). Cách tốt: Với mỗi phần tử giữa, dùng 2 con trỏ tìm 2 bên.

Chương trình minh họa

#include <iostream>
using namespace std;
void TripletsAP(int arr[], int n){
    for (int i = 1; i < n - 1; i++){
        for (int j = i - 1, k = i + 1; j >= 0 && k < n; ){
            if (arr[j] + arr[k] == 2 * arr[i]){
                cout << arr[j] << "\t" << arr[i] << "\t" << arr[k] << endl;
                k++; j--;
            }
            else if (arr[j] + arr[k] < 2 * arr[i]) k++;
            else j--;
        }
    }
}
int main(){
    int arr[] = {2, 5, 7, 8, 9, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Các bộ ba tạo thành cấp số cộng:\n";
    TripletsAP(arr, n);
    return 0;
}

Kết quả