C++에서 AP를 형성하는 정렬된 배열의 모든 삼중항 인쇄

이 문제에서는 정렬된 숫자 배열이 제공되며 산술 진행 형식의 are가 있는 삼중항을 찾아야 합니다.

산술 진행 연속된 항의 차이가 동일한 일련의 숫자입니다.

문제를 더 잘 이해하기 위해 예를 들어 보겠습니다 -

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

이 문제를 해결하기 위해 간단한 솔루션은 3개의 루프를 실행하고 AP에 있는 경우 모든 3중항을 확인하는 것입니다. 그러나 이 방법의 시간 복잡도는 n³ 입니다. .

더 나은 솔루션은 해싱을 사용하는 것입니다. 이 방법에서는 배열의 두 번째 요소부터 시작하여 모든 요소를 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에 있는 삼중항은 -