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

Trong bài toán này, chúng ta được đưa ra một dãy số đã được sắp xếp và chúng ta cần tìm các bộ ba có ở dạng tổng cộng.

Một cấp số cộng là một dãy số trong đó hiệu số giữa các số hạng liên tiếp giống nhau.

Hãy lấy một ví dụ để hiểu rõ hơn vấn đề -

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

Để giải quyết vấn đề này, một giải pháp đơn giản sẽ là chạy ba vòng và kiểm tra tất cả các bộ ba nếu chúng ở trong AP. nhưng phương pháp này có độ phức tạp về thời gian của thứ tự n ³ .

Một giải pháp tốt hơn là sử dụng băm. Trong phương pháp này, chúng ta sẽ bắt đầu từ phần tử thứ hai của mảng và coi mọi phần tử là phần tử giữa của AP và kiểm tra xem nó có tạo thành AP hay không.

Ví dụ

#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<<"The triplets that are in AP are : \n";
   TripletsAP(arr, n);
   return 0;
}

Đầu ra

Các bộ ba trong AP là -