Dos problemas de suma en Python
Resolver dos problemas de suma en Python
Su enfoque de este tema estará determinado por su nivel de experiencia. Un método es recorrer la lista, comparando cada elemento con el resto. Pasaremos por dos técnicas diferentes que puede usar para remediar este problema.
Planteamiento del problema: Devuelva todos los pares de dos números cuya suma es igual a un objetivo dado de una matriz de enteros. Puede suponer que cada entrada tiene una sola respuesta racional y que el mismo elemento no se puede reutilizar.
Comencemos explicando la declaración del problema y luego pasemos a las posibles soluciones. Esto realmente significa que necesitamos construir una función para verificar si hay algún valor en esta matriz que se suman al número de destino proporcionado. Proporcionaremos un ejemplo básico para describir el problema y la solución.
Suponga que nos dieron los números [4, 6, 1, -5, 8], y la suma objetivo era 9. Queremos ver si esta matriz tiene un par de números que se suman a la suma objetivo suministrada. Como puede ver, el procedimiento debe devolver 8 y 1, que resume hasta 9 como el total deseado. Entonces, ¿cuál es la mejor estrategia para lidiar con este problema?? Consulte las siguientes secciones:
Solución 1:
La primera respuesta que viene a la mente es repetir el bucle dos veces. La técnica nativa usa dos para bucles y viaja a través de la matriz completa dos veces para alcanzar la suma prevista.
Entonces, caminaríamos por la matriz uno a la vez. De esta manera, debe verificar el resto de la matriz para saber si la suma es igual al valor de número especificado mientras pasa por todos los números.
Por ejemplo, podemos continuar con 4 y avanzar en el resto de los números [6, 1, -5, 8] para determinar si agregar 4 a cualquiera de ellos proporciona 9 o no. Nos moveremos al siguiente número, 6, y verificaremos los números de la misma manera [1, -5, 8] para ver si agregar el número 6 a cualquiera de los números presentados en la matriz da 9, antes de continuar el proceso a través de la matriz. El código Python para un problema de dos suma con dos para bucles se muestra a continuación.
def twosumProb (my_arr, t_sum):para i en el rango (Len (my_arr) -1):
para j en rango (i, len (my_arr)):
Si my_arr [i]+my_arr [j] == t_sum:
return (my_arr [i]. my_arr [j])
devolver[]
La idea es resaltar que si bien hacerlo puede no ser el uso más eficiente del tiempo. Sigue siendo una opción viable. Dos para el bucle darán como resultado una complejidad del tiempo O (N2) ya que viajar dos veces utilizando dos para bucle significaría atravesar el tiempo N2 en términos de complejidad del tiempo. Debido a que no estamos almacenando ningún entero, la complejidad del espacio es O (1).
La segunda solución es un método de clasificación. Aunque el método puede ocupar más espacio, es más eficiente sin ninguna duda.
Solución 2:
Utilizaremos el algoritmo de clasificación de esta manera ya que la clasificación requiere Nlog (N) pasos de tiempo, que es considerablemente más eficiente que O (N2), empleado en la estrategia anterior con dos para bucles.
Los números de la matriz se ordenan primero en este enfoque. Tendremos dos punteros, uno a la izquierda al primer número en la matriz y el otro a la derecha en el último número de la matriz.
Simplificaremos este problema nuevamente utilizando el ejemplo de matriz anterior de [4, 6, 1, -5, 8]. Luego se clasifican los datos para reflejar una matriz ordenada de [-5, 1, 4, 6, 8]. Nuestro puntero izquierdo (indicado como l_pointer) se establecerá en -5 y nuestro puntero derecho (indicado como r_pointer) a 8. Veremos si -5 + 8 es igual a 9, que es el total especificado. No, porque 3 es menor que la suma declarada de 9. Cambiaremos nuestro cursor en orden ascendente, de izquierda a derecha.
Ahora volveremos a 1 y veremos si la adición de 1 y 8 es igual a 9, lo que hace. Esto nos da el par que estamos buscando. Los emparejamientos 1 y 8 ahora se imprimirán como los pares que proporcionarán las dos sumas numéricas requeridas.
Hablemos un poco más de este tema. Considere el siguiente escenario: si la suma objetivo es diez y la suma de uno y ocho es inferior a diez, el puntero izquierdo se moverá hasta cuatro en orden ascendente. El total de 4 y 8 es igual a 12, que es mayor que el total.
Como resultado, cambiaremos el puntero derecho en orden descendente de la posición derecha a la izquierda. El puntero izquierdo ahora está a las 4, mientras que el puntero derecho se ha movido a 6. En esta situación, hemos alcanzado el par requerido de 4 y 6, lo que nos dará la cantidad requerida de 10. El siguiente código de Python muestra cómo se implementa la información anterior a continuación:
def twosumProb (my_arr, t_sum):my_arr.clasificar()
l_pointer = 0
r_pointer = len (my_arr) -1
Mientras que l_pointer < r_pointer:
c_sum = my_arr [l_pointer]+my_arr [r_pointer]
Si c_sum == t_sum:
return (my_arr [l_pointer], my_arr [r_pointer])
Elif c_sum
demás:
r_pointer- = 1
devolver[]
Utilizamos O (NLOGN) en términos de complejidad del tiempo debido a la clasificación, que es mejor que el método de la solución anterior, y es un poco más caro porque usa O (NLOGN).
Conclusión:
En este artículo, examinamos el conocido problema de dos suma de Python y ofrecimos dos soluciones viables para que usted considere. Hemos agregado dos soluciones para solucionar este problema de dos suma en Python. Estos ejemplos se pueden aplicar de diferentes maneras según las necesidades del usuario. Esperamos que hayas encontrado útil el artículo. Consulte otros artículos de Sugerencia de Linux para obtener más consejos e información.