Programa Java para imprimir todos los tripletes en una array ordenada que forman AP

Dada una array ordenada de enteros positivos distintos, imprima todos los tripletes que forman
ejemplos AP (o progresión aritmética): 
 

Input : arr[] = { 2, 6, 9, 12, 17, 22, 31, 32, 35, 42 };
Output :
6 9 12
2 12 22
12 17 22
2 17 32
12 22 32
9 22 35
2 22 42
22 32 42

Input : arr[] = { 3, 5, 6, 7, 8, 10, 12};
Output :
3 5 7
5 6 7
6 7 8
6 8 10
8 10 12

Una solución simple es ejecutar tres bucles anidados para generar todos los tripletes y, para cada triplete, verificar si forma AP o no. La complejidad de tiempo de esta solución es O(n ³ )
Una mejor solución es usar hashing. Recorremos la array de izquierda a derecha. Consideramos cada elemento como medio y todos los elementos posteriores como elemento siguiente. Para buscar el elemento anterior, usamos una tabla hash.
 

// Java program to print all 
// triplets in given array 
// that form Arithmetic 
// Progression
import java.io.*;
import java.util.*;
  
class GFG
{
    // Function to print
    // all triplets in
    // given sorted array 
    // that forms AP
    static void printAllAPTriplets(int []arr,
                                   int n)
    {
        ArrayList<Integer> s = 
                 new ArrayList<Integer>();
        for (int i = 0;
                 i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                // Use hash to find if
                // there is a previous 
                // element with difference
                // equal to arr[j] - arr[i]
                int diff = arr[j] - arr[i];
                boolean exists = 
                        s.contains(arr[i] - diff);
                  
                if (exists)
                    System.out.println(arr[i] - diff + 
                                        " " + arr[i] + 
                                        " " + arr[j]);
            }
              
        s.add(arr[i]);
        }
    }
      
    // Driver code
    public static void main(String args[])
    {
        int []arr = {2, 6, 9, 12, 17, 
                     22, 31, 32, 35, 42};
        int n = arr.length;
        printAllAPTriplets(arr, n);
    }
}
  
// This code is contributed by 
// Manish Shaw(manishshaw1)

Producción :  

6 9 12
2 12 22
12 17 22
2 17 32
12 22 32
9 22 35
2 22 42
22 32 42

Complejidad temporal: O(n ² ) 
Espacio auxiliar: O(n)
Una solución eficiente se basa en el hecho de que la array está ordenada. Usamos el mismo concepto que se discutió en la pregunta del triplete GP . La idea es comenzar desde el segundo elemento y fijar cada elemento como un elemento medio y buscar los otros dos elementos en un triplete (uno más pequeño y otro más grande). 
A continuación se muestra la implementación de la idea anterior. 
 

// Java implementation to print
// all the triplets in given array
// that form Arithmetic Progression
   
import java.io.*;
   
class GFG 
{
       
    // Function to print all triplets in
    // given sorted array that forms AP
    static void findAllTriplets(int arr[], int n)
    {
           
        for (int i = 1; i < n - 1; i++) 
        {
       
            // Search other two elements 
            // of AP with arr[i] as middle.
            for (int j = i - 1, k = i + 1; j >= 0 && k < n;)
            {
                   
                // if a triplet is found
                if (arr[j] + arr[k] == 2 * arr[i]) 
                {
                    System.out.println(arr[j] +" " + 
                                       arr[i]+ " " + arr[k]);
       
                    // Since elements are distinct,
                    // arr[k] and arr[j] cannot form
                    // any more triplets with arr[i]
                    k++;
                    j--;
                }
       
                // If middle element is more move to 
                // higher side, else move lower side.
                else if (arr[j] + arr[k] < 2 * arr[i]) 
                    k++;         
                else
                    j--;         
            }
        }
    }
   
    // Driver code
    public static void main (String[] args) 
    {
           
        int arr[] = { 2, 6, 9, 12, 17, 
                      22, 31, 32, 35, 42 };
        int n = arr.length;
           
        findAllTriplets(arr, n);
    }
}
   
// This code is contributed by vt_m.

Producción :  

6 9 12
2 12 22
12 17 22
2 17 32
12 22 32
9 22 35
2 22 42
22 32 42

Complejidad de tiempo: O(n ² ) 
Espacio auxiliar: O(1)
Consulte el artículo completo sobre Imprimir todos los tripletes en una array ordenada que forman AP para obtener más detalles.