Jardin de Conocimiento

LeetCode 15 — 3Sum

9 min read

LeetCode 15 — 3Sum

Tercer problema del patrón Two Pointers y uno de los más icónicos de LeetCode. Combina sort + fix one + two pointers para resolver una extensión natural de Two Sum: tripletas que suman cero. Aprenderlo bien abre 4Sum, K-Sum y muchas variantes. La parte difícil no es la idea, es manejar duplicados sin un set auxiliar. Eso es lo que se aprende aquí.

Enunciado

Dado un array de enteros nums, devuelve todas las tripletas únicas [nums[i], nums[j], nums[k]] tales que:

  • i != j, i != k, j != k,
  • nums[i] + nums[j] + nums[k] == 0.

El conjunto de soluciones no debe contener tripletas duplicadas.

Ejemplo 1:

Input:  nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
        Explicación:
          -1 + 0 + 1 = 0
          -1 + (-1) + 2 = 0
        (-1, 0, 1) y (0, 1, -1) y (1, -1, 0) son la MISMA tripleta — solo aparece una vez

Ejemplo 2:

Input:  nums = [0, 1, 1]
Output: []

Ejemplo 3:

Input:  nums = [0, 0, 0]
Output: [[0, 0, 0]]

Restricciones:

  • 3 <= nums.length <= 3000.
  • -10^5 <= nums[i] <= 10^5.

Plantilla:

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ...

Lectura del problema antes de codear

PreguntaRespuesta
¿Qué tipo devuelve?List[List[int]] — lista de tripletas
¿Tripletas únicas?SÍ — sin duplicados (esto es el reto principal)
¿Importa el orden interno de la tripleta?NO — [-1, 0, 1] y [0, 1, -1] cuentan como la misma
¿Importa el orden de las tripletas en la lista?NO
¿Está ordenado el array?NO (pero vamos a ordenarlo)
¿Pueden los tres elementos ser iguales?Sí, si suman 0: [0, 0, 0] es válida
Edge case 1nums = [0, 0, 0, 0] → solo “ (no duplicada)
Edge case 2nums = [1, 2, 3] → [] (no hay tripleta que sume 0)

Solución 1 — Fuerza bruta con set (NO recomendada)

Triple bucle, deduplicar con set de tuplas ordenadas.

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        resultado = set()
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    if nums[i] + nums[j] + nums[k] == 0:
                        triplete = tuple(sorted([nums[i], nums[j], nums[k]]))
                        resultado.add(triplete)
        return [list(t) for t in resultado]

Análisis:

  • Tiempo: O(n³) — TLE con n = 3000 (27 mil millones de operaciones).
  • Espacio: O(n²) en el peor caso para el set.
  • Veredicto: [NO] rechazada.

Solución 2 — Sort + fix one + two pointers (la canónica)

La idea clave: ordenar primero. Para cada índice i, fijar nums[i] como el primer elemento del triplete. Buscar dos elementos que sumen -nums[i] en el subarray ordenado a la derecha de i usando two pointers (como 167-two-sum-ii-input-array-is-sorted).

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        resultado = []
 
        for i in range(n - 2):                          # i hasta n-3 (deja espacio para left, right)
            # 🔑 Saltar duplicados de i
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            # ⚡ Optimización: si nums[i] > 0, ya no puede sumar 0
            if nums[i] > 0:
                break
 
            left, right = i + 1, n - 1
            while left < right:
                suma = nums[i] + nums[left] + nums[right]
                if suma == 0:
                    resultado.append([nums[i], nums[left], nums[right]])
                    # 🔑 Saltar duplicados de left y right
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif suma < 0:
                    left += 1
                else:
                    right -= 1
 
        return resultado

Análisis paso a paso

Trace mental con nums = [-1, 0, 1, 2, -1, -4]:

Después del sort: nums = [-4, -1, -1, 0, 1, 2].

inums[i]Acción(left, right) inicialResultado parcial
0-4Buscar suma = 4 con left=1, right=5(1, 5)nada (-4+-1+2=-3, … no encuentra)
1-1Buscar suma = 1(2, 5)-1+-1+2=0 [OK] → append [-1,-1,2]. Avanzar saltando dup
1 (sigue)-1(left=3, right=4)-1+0+1=0 [OK] → append [-1,0,1]
2-1DUP de i=1 → skip——
30Buscar suma = 0(4, 5)0+1+2=3, no, no encuentra
41nums[i] > 0 → break——

Resultado final: [[-1, -1, 2], [-1, 0, 1]] [OK]

Por qué los tres “saltar duplicados” son críticos

Skip 1 — duplicados de i:

if i > 0 and nums[i] == nums[i - 1]:
    continue

Si dos i consecutivos tienen el mismo valor, generarían las mismas tripletas (con left/right en el mismo subespacio). Saltar i evita duplicar.

Skip 2 — duplicados de left después de match:

while left < right and nums[left] == nums[left + 1]:
    left += 1
left += 1

Si tras encontrar un match, el siguiente left tiene el mismo valor, generaría la misma tripleta. Saltar.

Skip 3 — duplicados de right después de match: análogo a left.

Optimización (early break):

if nums[i] > 0:
    break

Después del sort, si nums[i] > 0, todos los siguientes son ≥ nums[i]. La suma de tres positivos no puede ser 0.

Análisis:

  • Tiempo: O(n²) — sort O(n log n) + bucle externo n veces × bucle interno O(n) = O(n²).
  • Espacio: O(1) extra (excluyendo output) o O(n) si sort() no es in-place.
  • Veredicto: [OK] la respuesta esperada. La óptima conocida.

El patrón general — “Sort + fix one + two pointers” (reducción a 2-Sum)

Cuándo aplicar:

Cuando el problema pide encontrar k elementos que cumplen una relación aritmética (suma, producto), y el array no está ordenado. Ordenar reduce el problema k-Sum a (k-1)-Sum mediante fixing.

Plantilla mental (3-Sum):

def k_sum_pattern(arr, k, target):
    arr.sort()
    if k == 2:
        return two_sum_two_pointers(arr, target)    # caso base
    resultado = []
    for i in range(len(arr) - k + 1):
        if i > 0 and arr[i] == arr[i-1]:
            continue                                # skip dup
        sub = k_sum_pattern(arr[i+1:], k-1, target - arr[i])
        for s in sub:
            resultado.append([arr[i]] + s)
    return resultado

Tres señales del patrón:

  1. Buscas k-tuplas con relación aritmética.
  2. El array no es ordenado (o se permite ordenar).
  3. Necesitas evitar duplicados en el output.

Variaciones del problema

Problema LeetCodeVariación
167. Two Sum II - Input Array Is SortedCaso base k=2
16. 3Sum ClosestTripleta con suma más cercana al target → mismo patrón con tracking de mejor diferencia
18. 4Sumk=4 → dos fixes anidados + two pointers
259. 3Sum SmallerCuántas tripletas con suma < target
611. Valid Triangle NumberTripletas que cumplen desigualdad triangular

Conceptos a interiorizar

nums.sort() vs sorted(nums)

nums.sort()              # in-place, devuelve None, modifica nums
nums = sorted(nums)      # crea nueva lista, no modifica original

En LeetCode, modificar el input a veces es aceptable (a veces no — preguntar al entrevistador). Para 3Sum es estándar modificarlo.

Saltar duplicados sin set auxiliar

La técnica clave aquí es: “si soy igual a mi vecino anterior, ya he hecho ese trabajo”.

# Patrón general
for i in range(len(arr)):
    if i > 0 and arr[i] == arr[i-1]:
        continue
    # ... procesamiento ...

Esto solo funciona si el array está ordenado (los duplicados están consecutivos).

Three pointers vs Two pointers

3Sum usa 3 índices: i (fixo) + left y right (two pointers en el resto). No es “three pointers” en el sentido formal — es “fixed + two pointers”.

Comparación final de las 2 soluciones

SoluciónTiempoEspacioVeredicto
1. Fuerza bruta + setO(n³)O(n²)[NO] TLE
2. Sort + fix + two pointersO(n²)O(1) extra[OK] La óptima

Auto-test (para ti, sin mirar el archivo)

  1. Escribe la Solución 2 desde cero.
  2. Justifica los tres lugares donde se saltan duplicados, y qué duplicados generaría no saltar cada uno.
  3. Trace mental con nums = [0, 0, 0, 0]. ¿Resultado? ¿Cuántas veces entra al bucle interno?
  4. Trace mental con nums = [-2, 0, 1, 1, 2]. Identifica las tripletas válidas.
  5. Bonus — extiende a 4-Sum (a + b + c + d == target). Pista: dos bucles externos + two pointers.
  6. Bonus 2 — explica la optimización if nums[i] > 0: break. ¿Por qué es correcta? ¿Cuánto ahorra?

Cosas que te pueden preguntar en entrevista

  • “¿Por qué ordenar primero?” → Permite (a) usar two pointers en el subarray, (b) saltar duplicados con == al vecino anterior, sin set auxiliar.
  • “¿Cuál es el caso peor de tu algoritmo?” → O(n²) cuando hay muchas tripletas que evaluar (e.g. nums = [0]*n aunque ahí solo hay una tripleta válida y se descarta rápido).
  • “¿Y si el target no fuera 0 sino arbitrario?” → Misma técnica, cambias suma == 0 por suma == target y suma < 0 por suma < target.
  • “¿Por qué no usas un set para deduplicar?” → Porque el array está ordenado, los duplicados son consecutivos y se saltan en O(1) sin estructura auxiliar.
  • “¿Cómo extenderías a k-Sum genérico?” → Recursión con caso base 2-Sum (two pointers). Complejidad O(n^(k-1)).

Solución en C++ — contraste con Python

Añadido para ver las diferencias de lenguaje. Código compilable en 15-3sum.cpp.

class Solution {
 public:
  std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    std::vector<std::vector<int>> res;
    int n = (int)nums.size();
    for (int i = 0; i < n - 2; ++i) {
      if (i > 0 && nums[i] == nums[i - 1]) continue;     // pivote duplicado
      int lo = i + 1, hi = n - 1;
      while (lo < hi) {
        int sum = nums[i] + nums[lo] + nums[hi];
        if (sum < 0) ++lo;
        else if (sum > 0) --hi;
        else {
          res.push_back({nums[i], nums[lo], nums[hi]});
          ++lo; --hi;
          while (lo < hi && nums[lo] == nums[lo - 1]) ++lo;
          while (lo < hi && nums[hi] == nums[hi + 1]) --hi;
        }
      }
    }
    return res;
  }
};

Análisis: Tiempo O(n²), Espacio O(1) extra (sin contar la salida) — igual que el Python con sort + two pointers.

Diferencias clave Python ↔ C++:

  • nums.sort() → std::sort(nums.begin(), nums.end()).
  • Listas anidadas res.append([a,b,c]) → res.push_back({a,b,c}) (lista de inicialización del vector<int> interno).
  • Sin enumerate; índices enteros explícitos y cuidado con n - 2 (evita size() sin signo en restas: castea a int).
  • La lógica de saltar duplicados es idéntica; el coste de comparar enteros es trivial en ambos.

Conexiones

Estado de progreso personal

  • Leído con comprensión
  • Escrita Solución 2 desde cero
  • Justificados los 3 lugares de salto de duplicados
  • Trace mental con [0, 0, 0, 0] y [-2, 0, 1, 1, 2]
  • Resuelto en LeetCode con éxito
  • Implementada extensión a 4-Sum (Bonus 1)

Graph View

Backlinks