Programa Python3 para contar trillizos con una suma menor que un valor dado

Dada una array de enteros distintos y un valor de suma. Encuentre el recuento de trillizos con una suma menor que el valor de suma dado. La Complejidad Temporal esperada es O(n ² ).
Ejemplos: 
 

Input : arr[] = {-2, 0, 1, 3}
        sum = 2.
Output : 2
Explanation :  Below are triplets with sum less than 2
               (-2, 0, 1) and (-2, 0, 3) 

Input : arr[] = {5, 1, 3, 4, 7}
        sum = 12.
Output : 4
Explanation :  Below are triplets with sum less than 12
               (1, 3, 4), (1, 3, 5), (1, 3, 7) and 
               (1, 4, 5)

Una solución simple es ejecutar tres bucles para considerar todos los tripletes uno por uno. Para cada triplete, compare las sumas e incremente el conteo si la suma del triplete es menor que la suma dada. 
 

# A Simple Python 3 program to count triplets with sum smaller
# than a given value
  
def countTriplets(arr, n, sum):
  
    # Initialize result
    ans = 0
  
    # Fix the first element as A[i]
    for i in range( 0 ,n-2):
      
        # Fix the second element as A[j]
        for j in range( i+1 ,n-1):
      
            # Now look for the third number
            for k in range( j+1, n):
                if (arr[i] + arr[j] + arr[k] < sum):
                    ans+=1
      
    return ans
  
# Driver program
arr = [5, 1, 3, 4, 7]
n = len(arr)
sum = 12
print(countTriplets(arr, n, sum))
  
#Contributed by Smitha

Producción: 

4

La complejidad temporal de la solución anterior es O(n ³ ). Una solución eficiente puede contar trillizos en O (n ² ) ordenando la array primero y luego usando el método 1 de esta publicación en un bucle.
 

1) Sort the input array in increasing order.
2) Initialize result as 0.
3) Run a loop from i = 0 to n-2.  An iteration of this loop finds all
   triplets with arr[i] as first element.
     a) Initialize other two elements as corner elements of subarray
        arr[i+1..n-1], i.e., j = i+1 and k = n-1
     b) Move j and k toward each other until they meet, i.e., while (j= sum
                then k--
            // Else for current i and j, there can (k-j) possible third elements
            // that satisfy the constraint.
            (ii) Else Do ans += (k - j) followed by j++ 

A continuación se muestra la implementación de la idea anterior. 
 

# Python3 program to count triplets with 
# sum smaller than a given value 
  
  
# Function to count triplets with sum smaller
# than a given value         
def countTriplets(arr,n,sum):
      
    # Sort input array
    arr.sort()
      
    # Initialize result 
    ans = 0
      
    # Every iteration of loop counts triplet with 
    # first element as arr[i].
    for i in range(0,n-2):
          
        # Initialize other two elements as corner elements 
        # of subarray arr[j+1..k] 
        j = i + 1
        k = n-1
  
        # Use Meet in the Middle concept 
        while(j < k):
              
            # If sum of current triplet is more or equal, 
            # move right corner to look for smaller values
            if (arr[i]+arr[j]+arr[k] >=sum):
                k = k-1
              
            # Else move left corner 
            else:
                  
                # This is important. For current i and j, there 
                # can be total k-j third elements. 
                ans += (k - j)
                j = j+1
      
    return ans
  
# Driver program 
if __name__=='__main__':
    arr = [5, 1, 3, 4, 7] 
    n = len(arr) 
    sum = 12
    print(countTriplets(arr, n, sum)) 
      
# This code is contributed by 
# Yatin Gupta 

Producción: 

4

¡ Consulte el artículo completo sobre Contar trillizos con una suma menor que un valor dado para obtener más detalles!