C++でAPを形成するソートされた配列のすべてのトリプレットを出力します

この問題では、並べ替えられた数値の配列が与えられ、算術プログレッションの形式のトリプレットを見つける必要があります。

等差数列 は、連続する用語間の差が同じである一連の数値です。

問題をよりよく理解するために例を見てみましょう-

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

この問題を解決するための簡単な解決策は、3つのループを実行し、すべてのトリプレットがAPにあるかどうかをチェックすることです。ただし、この方法では、n ³ のオーダーの時間計算量があります。 。

より良い解決策は、ハッシュを使用することです。この方法では、配列の2番目の要素から開始し、すべての要素をAPの中間要素として扱い、APを形成するかどうかを確認します。

例

#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;
}

出力

APにあるトリプレットは-

2 5 8
5 7 9
7 8 9
8 9 10