3Sum

Last updated May 26, 2024 Edit Source

• Leetcode
• Interviewprep

• Ordena el array para utilizar la tecnica de Two Pointers (Se puede utilizar Arrays.sort() o Merge Sort o cualquier otro algoritmo)
• Itera sobre cada elemento del array. Para cada uno inicializa dos punteros
  • El puntero de lzquierda ira en i + 1, debido a que todas las combinaciones anteriores a i ya fueron probadas por el puntero de la izquierda, ya no se necesita recorrerlas nuevamente
  • El puntero de la derecha ira en i.length - 1
• Itera mientras izquierda no llegue a tener el mismo valor que derecha
• Calcula la suma del triplete actual usando, i, izquierda y derecha.
• Si la suma es igual al valor target retorna true
• Si es menor, incrementa el puntero de la izquierda
• Si es mayor, incrementa el puntero de la derecha
• Si llegas al final del array y sales del loop retorna false, porque no hubo ningun triplete que diera como resultado target

En esta solucion se transforma al problema de three sum en un two sum. Para ello, se ordena el array y se utiliza un forin loop.

Primero, definimos el array que contendra los triplets como solucion. Posteriormente, sorteamos el array.

Se inicia el recorrido. En la primer condicional, checamos que el numero actual sea diferente al anterior, de esta forma podemos asegurarnos que es la primera vez que estamos encontrando un triplete con este numero.

A partir de aqui, nos encontramos en un two-sum un poco modificado y debido a que esta sorted podemos usar two-pointers. Primero, definimos el numero target que buscamos.

Definimos el primer puntero como el siguiente al indice actual que tenemos en nuestro elemento, de esta forma podemos asegurarnos que no haremos comparaciones con elementos sobre los cuales estamos seguros que ya buscamos sus tripletes.

En escencia, buscamos los tripletes de cada elemento unico dentro de la lista.

Posteriormente, definimos el ultimo elemento del array. Este sera el ultimo del array.

Ahora iteramos sobre los elementos entre estos dos punteros, obtenemos su suma y checamos si es menor o mayor al target, esta logica es similar al problema TwoSum II.

En el caso else, agregamos el triplete al array, incrementamos nuestro primer puntero y lo seguimos incrementando hasta encontrar uno que sea diferente al que acabamos de recibar, con esto nuevamente buscamos tripletes que sean unicos. En caso no encontrarlo terminaremos dicha busqueda y pasaremos al siguiente elemento.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        triplets = []
        nums.sort()
        for zero in range(0, len(nums)):
            if zero > 0 and nums[zero] == nums[zero - 1]:
                continue

            target = -(0 + nums[zero])
            one = zero + 1
            two = len(nums) - 1
            
            while one < two:
                sum = nums[one] + nums[two]
                if sum < target:
                    one += 1
                elif sum > target:
                    two -= 1
                else:
                    triplets.append([nums[zero], nums[one], nums[two]])
                    one += 1
                    while nums[one] == nums[one-1] and one < two:
                        one += 1
        return triplets