Dada una array de números enteros, debe encontrar tres números tales que la suma de dos elementos sea igual al tercer elemento.
Ejemplos:
Input: {5, 32, 1, 7, 10, 50, 19, 21, 2} Output: 21, 2, 19 Input: {5, 32, 1, 7, 10, 50, 19, 21, 0} Output: no such triplet exist
Fuente de la pregunta: experiencia de entrevista con Arcesium | Conjunto 7 (En el campus para prácticas)
Enfoque simple: ejecute tres bucles y verifique si existe un triplete tal que la suma de dos elementos sea igual al tercer elemento.
Complejidad del tiempo : O(n^3)
Enfoque eficiente: La idea es similar a Encontrar un triplete que sume un valor dado.
- Primero ordene la array dada.
- Comience a fijar el mayor elemento de tres desde atrás y recorra la array para encontrar los otros dos números que suman el tercer elemento.
- Tome dos punteros j (desde el frente) y k (inicialmente i-1) para encontrar el menor de los dos números y desde i-1 para encontrar el mayor de los dos números restantes
- Si la suma de ambos números sigue siendo menor que A[i], entonces necesitamos aumentar el valor de la suma de dos números, aumentando así el puntero j, para aumentar el valor de A[j] + A[ k] .
- Si la suma de ambos números es mayor que A[i], entonces debemos disminuir el valor de la suma de dos números, por lo tanto, disminuir el puntero k para disminuir el valor total de A[j] + A[k ] .
La imagen de abajo es una ejecución en seco del enfoque anterior:
A continuación se muestra la implementación del enfoque anterior:
Javascript
<script> // Javascript program to find three numbers // such that sum of two makes the // third element in array // Utility function for finding // triplet in array function findTriplet(arr, n) { // Sort the array arr.sort((a,b) => a-b); // For every element in arr check // if a pair exist(in array) whose // sum is equal to arr element for (let i = n - 1; i >= 0; i--) { let j = 0; let k = i - 1; // Iterate forward and backward to // find the other two elements while (j < k) { // If the two elements sum is // equal to the third element if (arr[i] == arr[j] + arr[k]) { // Pair found document.write("numbers are " + arr[i] + " " + arr[j] + " " + arr[k] + "<br>"); return; } // If the element is greater than // sum of both the elements, then try // adding a smaller number to reach the // equality else if (arr[i] > arr[j] + arr[k]) j += 1; // If the element is smaller, then // try with a smaller number // to reach equality, so decrease K else k -= 1; } } // No such triplet is found in array document.write("No such triplet exists"); } // Driver code let arr = [5, 32, 1, 7, 10, 50, 19, 21, 2]; let n = arr.length; findTriplet(arr, n); // This code is contributed by Mayank Tyagi </script>
Producción:
numbers are 21 2 19
Complejidad del tiempo : O(N^2)
Otro enfoque: la idea es similar al enfoque anterior.
- Ordenar la array dada.
- Inicie un bucle anidado, fijando el primer elemento i (de 0 a n-1) y moviendo el otro j (de i+1 a n-1).
- Tome la suma de ambos elementos y búsquelo en la array restante usando la búsqueda binaria.
Javascript
<script> // Javascript program to find three numbers // such that sum of two makes the // third element in array bool search(sum, start, end, arr) { while (start <= end) { let mid = (start + end) / 2; if (arr[mid] == sum) { return true; } else if (arr[mid] > sum) { end = mid - 1; } else { start = mid + 1; } } return false; } // Utility function for finding // triplet in array function findTriplet(arr, n) { // Sort the array arr.sort((a,b) => a-b); // Initialising nested loops for (let i = 0; i < n; i++) { for (let j = i + 1; j < n; j++) { if (search((arr[i] + arr[j]), j, n - 1, arr)) { document.write("numbers are " + arr[i] + " " + arr[j] + " " + ( arr[i] + arr[j] ) + "<br>"); } } } // No such triplet is found in array document.write("No such triplet exists"); } // Driver code let arr = [5, 32, 1, 7, 10, 50, 19, 21, 2]; let n = arr.length; findTriplet(arr, n); </script> // This code is contributed by Sarthak Delori
Complejidad del tiempo: O(N^2*log N)
Complejidad espacial: O(1)
Consulte el artículo completo sobre Encontrar un triplete tal que la suma de dos sea igual al tercer elemento para obtener más detalles.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA