Contar trillizos tales que la suma de dos números sea igual al tercero | conjunto 2

Dada una array de enteros positivos distintos arr[] de longitud N , la tarea es contar todos los tripletes de modo que la suma de dos elementos sea igual al tercer elemento.

Ejemplos:  

Entrada: arr[] = {1, 5, 3, 2} 
Salida: 2 
Explicación: 
En la array dada, hay dos tripletas tales que la suma de los dos números es igual al tercer número, esos son – ( 
1, 2, 3), (3, 2, 5)
Entrada: arr[] = {3, 2, 7} 
Salida: 0 
Explicación: 
En la array dada no existen tripletas tales que la suma de dos números sea igual al tercero número.  

Enfoque: la idea es crear una array de frecuencia de los números que están presentes en la array y luego verificar para cada par del elemento que la suma de los elementos del par está presente en la array o no con la ayuda de la array de frecuencia en O (1 vez.
Algoritmo:  

• Declare una array de frecuencia para almacenar la frecuencia de los números.
• Iterar sobre los elementos de la array e incrementar la cuenta de ese número en la array de frecuencia.
• Ejecute dos bucles para elegir dos índices diferentes de la array y verifique si la suma de los elementos en esos índices tiene una frecuencia mayor que 0 en la array de frecuencia.

If frequency of the sum is greater than 0:
    Increment the count of the triplets.

Nota : hemos asumido en el programa que el valor de los elementos de la array se encuentra en el rango [1, 100].
A continuación se muestra la implementación del enfoque anterior:
 

// C++ implementation to count the
// triplets such that the sum of the
// two numbers is equal to third number
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the count of the
// triplets such that sum of two
// numbers is equal to the third number
int countTriplets(int arr[], int n){
    int freq[100] = {0};
     
    // Loop to count the frequency
    for (int i=0; i < n; i++){
        freq[arr[i]]++;
    }
    int count = 0;
     
    // Loop to count for triplets
    for(int i = 0;i < n; i++){
        for(int j = i+1; j < n; j++){
            if(freq[arr[i] + arr[j]]){
                count++;
            }
        }
    }
    return count;
}
 
// Driver Code
int main()
{
    int n = 4;
    int arr[] = {1, 5, 3, 2};
     
    // Function Call
    cout << countTriplets(arr, n);
    return 0;
}

// Java implementation to count the
// triplets such that the sum of the
// two numbers is equal to third number
class GFG{
 
// Function to find the count of the
// triplets such that sum of two
// numbers is equal to the third number
static int countTriplets(int arr[], int n){
    int []freq = new int[100];
     
    // Loop to count the frequency
    for (int i = 0; i < n; i++){
        freq[arr[i]]++;
    }
    int count = 0;
     
    // Loop to count for triplets
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(freq[arr[i] + arr[j]] > 0){
                count++;
            }
        }
    }
    return count;
}
 
// Driver Code
public static void main(String[] args)
{
    int n = 4;
    int arr[] = {1, 5, 3, 2};
     
    // Function Call
    System.out.print(countTriplets(arr, n));
}
}
 
// This code is contributed by Rajput-Ji

# Python 3 implementation to count the
# triplets such that the sum of the
# two numbers is equal to third number
 
# Function to find the count of the
# triplets such that sum of two
# numbers is equal to the third number
def countTriplets(arr, n):
    freq = [0 for i in range(100)]
     
    # Loop to count the frequency
    for i in range(n):
        freq[arr[i]] += 1
    count = 0
     
    # Loop to count for triplets
    for i in range(n):
        for j in range(i + 1, n, 1):
            if(freq[arr[i] + arr[j]]):
                count += 1
    return count
 
# Driver Code
if __name__ == '__main__':
    n = 4
    arr = [1, 5, 3, 2]
     
    # Function Call
    print(countTriplets(arr, n))
 
# This code is contributed by Surendra_Gangwar

// C# implementation to count the
// triplets such that the sum of the
// two numbers is equal to third number
using System;
 
class GFG{
 
// Function to find the count of the
// triplets such that sum of two
// numbers is equal to the third number
static int countTriplets(int []arr, int n){
    int []freq = new int[100];
     
    // Loop to count the frequency
    for (int i = 0; i < n; i++){
        freq[arr[i]]++;
    }
    int count = 0;
     
    // Loop to count for triplets
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(freq[arr[i] + arr[j]] > 0){
                count++;
            }
        }
    }
    return count;
}
 
// Driver Code
public static void Main(string[] args)
{
    int n = 4;
    int []arr = {1, 5, 3, 2};
     
    // Function Call
    Console.WriteLine(countTriplets(arr, n));
}
}
 
// This code is contributed by Yahs_R

<script>
 
// Javascript implementation to count the
// triplets such that the sum of the
// two numbers is equal to third number
 
 
// Function to find the count of the
// triplets such that sum of two
// numbers is equal to the third number
function countTriplets(arr, n){
    let freq = new Uint8Array(100);
     
    // Loop to count the frequency
    for (let i=0; i < n; i++){
        freq[arr[i]]++;
    }
    let count = 0;
     
    // Loop to count for triplets
    for(let i = 0;i < n; i++){
        for(let j = i+1; j < n; j++){
            if(freq[arr[i] + arr[j]]){
                count++;
            }
        }
    }
    return count;
}
 
// Driver Code
    let n = 4;
    let arr = [1, 5, 3, 2];
     
    // Function Call
    document.write(countTriplets(arr, n));
     
//This code is contributed by Mayank Tyagi
</script>

2

Análisis de rendimiento:  

• Complejidad Temporal: O(N ² ).
• Espacio Auxiliar: O(N).