Solución 3sum Leetcode en Python

El problema 3Sum en LeetCode nos desafía a encontrar todos los tripletes únicos en una matriz cuya suma sea cero. Este problema implica una manipulación compleja de matrices y la exploración de diferentes enfoques algorítmicos. En este artículo, analizaremos el proceso de resolución utilizando Brute Force, Better Solution y Optimal Solution.

Planteamiento del problema

Dado el rango completo numsdevolver todos los trillizos [nums[i], nums[j], nums[k]] tal que i != j, i != ky j != ky nums[i] + nums[j] + nums[k] == 0. El conjunto de solución no debe contener tripletes duplicados.

Enlace al problema de Leetcode – https://leetcode.com/problems/3sum/description/

Enfoque de fuerza bruta:

El enfoque más sencillo para resolver el problema 3Sum es mediante un método de fuerza bruta. La idea es generar todos los tripletes posibles y comprobar si su suma es igual a cero. Si bien este método puede funcionar, es muy ineficiente, especialmente para matrices de entrada grandes.

def threeSumBruteForce(nums):
    result = []
    nums.sort()
    
    for i in range(len(nums) - 2):
        for j in range(i + 1, len(nums) - 1):
            for k in range(j + 1, len(nums)):
                triplet_sum = nums[i] + nums[j] + nums[k]
                if triplet_sum == 0:
                    result.append([nums[i], nums[j], nums[k]])
    
    return result

La complejidad temporal de esta solución es O(n^3), lo que la hace poco práctica para conjuntos de datos grandes.

¿Por qué el enfoque de Fuerza Bruta es ineficiente para resolver el problema 3Sum?

El enfoque de Fuerza Bruta implica generar todos los tripletes posibles en la matriz y verificar si su suma es igual a cero. Esto lleva a una complejidad temporal de O(n^3), lo que lo hace poco práctico para grandes conjuntos de datos. El algoritmo explora combinaciones redundantes, lo que da como resultado un rendimiento deficiente.

Mejor solución:

Para mejorar el enfoque de Fuerza Bruta, podemos utilizar una técnica de dos puntos. Al elegir el rango, podemos explorar combinaciones de manera eficiente sin cálculos adicionales.

def threeSumBetter(nums):
    result = []
    nums.sort()
    
    for i in range(len(nums) - 2):
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            triplet_sum = nums[i] + nums[left] + nums[right]
            
            if triplet_sum == 0:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif triplet_sum < 0:
                left += 1
            else:
                right -= 1
    
    return result

Esta solución tiene una complejidad temporal de O(n^2), una mejora significativa con respecto al método de fuerza bruta.

¿Cómo mejora la técnica de dos puntos la solución hasta convertirla en una «mejor solución»?

La técnica de dos punteros se emplea en la «Mejor solución» para mejorar la eficiencia. Al seleccionar la matriz, el algoritmo puede usar dos punteros para explorar combinaciones de manera eficiente sin cálculos adicionales. Esto reduce la complejidad del tiempo a O(n^2) en contraposición a O(n^3) del enfoque de Fuerza Bruta.

¿Cuál es la importancia de la selección de rango en las soluciones de dos punteros?

La selección de rango es crucial para las soluciones Two-Pointer, ya que permite una exploración organizada y eficiente de combinaciones. Permite que el algoritmo ajuste rápidamente los punteros basándose en la comparación de la suma triplete con el valor objetivo (cero). La clasificación facilita la identificación y omisión de valores duplicados, optimizando el proceso general.

Solucion optima:

La solución óptima explota la técnica de dos punteros y al mismo tiempo optimiza aún más el código.

def threeSumOptimal(nums):
    result = []
    nums.sort()
    
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            triplet_sum = nums[i] + nums[left] + nums[right]
            
            if triplet_sum == 0:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                
                while left < right and nums[left] == nums[left - 1]:
                    left += 1
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1
            elif triplet_sum < 0:
                left += 1
            else:
                right -= 1
    
    return result

Esta solución óptima mantiene la complejidad del tiempo O(n^2) pero evita más tripletes duplicados de manera más eficiente.

¿Cómo mejora aún más la «Solución Óptima» la eficiencia de la técnica de dos punteros?

La «Solución óptima» se basa en la técnica de dos puntos al incorporar comprobaciones adicionales para omitir de manera eficiente elementos duplicados. Esto incluye comprobaciones para evitar cálculos excesivos y garantizar que los tripletes resultantes sean únicos. La «solución óptima» mantiene una complejidad temporal O(n^2) y minimiza los cálculos innecesarios.

¿Cuál es la complejidad temporal del problema de la solución óptima de las tres sumas?

La solución óptima al problema 3Sum tiene una complejidad temporal de O (n ^ 2). Esto se logra utilizando la técnica de dos punteros e incorporando optimizaciones para omitir de manera eficiente elementos duplicados. El rendimiento del algoritmo mejora significativamente en comparación con el enfoque de Fuerza Bruta.

Algo que te pueda gustar: