Two-sum y sus numerosas variantes
Resuelva two-sum, three-sum, four-sum y two-sum with sorted array usando mapas hash y dos punteros, y compare los costes temporales y espaciales.
Two-sum y sus numerosas variantes es una lección gratuita de DSA Interview Prep en CoddyKit. Esta es la lección 2 de 4. Puedes leer la lección completa abajo gratuitamente — luego la practicas en el navegador con un editor de código integrado y un tutor de IA 24/7. Forma parte de la ruta de aprendizaje de DSA Interview Prep, y tu progreso se sincroniza en la web y la app de CoddyKit. El curso de DSA Interview Prep incluye 4 lecciones en total.
Two-Sum: el problema clásico de entrevistas
LeetCode 1 «Two Sum»: dado un array desordenado y un target, devuelva los índices de dos elementos cuya suma sea target. El enfoque de fuerza bruta O(n²) comprueba todos los pares. El enfoque óptimo O(n) utiliza un mapa hash: para cada elemento x, compruebe si target - x ya existe en el mapa. Si es así, devuelva el par de índices. Si no, almacene x y su índice en el mapa.
Two-sum suele ser el primer problema de una entrevista; dominarlo completamente indica que está preparado para pasar a problemas más difíciles.
def twoSum(nums, target):
seen = {} # val -> index
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
return [seen[complement], i]
seen[x] = i
return []
print(twoSum([2, 7, 11, 15], 9)) # [0, 1]
print(twoSum([3, 2, 4], 6)) # [1, 2]
print(twoSum([3, 3], 6)) # [0, 1]Por qué funciona el mapa hash para Two-Sum
El mapa hash almacena todos los elementos vistos hasta el momento. Al procesar el elemento x, si target - x está en el mapa, esos dos elementos forman un par válido. Es fundamental comprobar siempre el complemento antes de almacenar x, ya que así se evita emparejar un elemento consigo mismo (por ejemplo, si x == target/2, la comprobación del mapa se realiza antes de almacenar x, por lo que no coincidirá a menos que haya dos copias).
# Trace two-sum on [2, 7, 11, 15], target=9
nums, target = [2, 7, 11, 15], 9
seen = {}
for i, x in enumerate(nums):
complement = target - x
print(f'i={i} x={x} complement={complement} seen={seen}')
if complement in seen:
print(f' Found: indices [{seen[complement]}, {i}]')
break
seen[x] = iTwo-Sum en un array ordenado (dos punteros)
Si el array ya está ordenado y necesita los índices de los valores (no los índices originales), utilice la técnica de dos punteros: los punteros left y right comienzan en extremos opuestos. Si la suma es igual a target, devuelva el resultado. Si la suma es demasiado pequeña, avance left hacia la derecha. Si es demasiado grande, mueva right hacia la izquierda. Esto requiere O(n) de tiempo y O(1) de espacio, por lo que es mejor que el enfoque del mapa hash cuando el array está ordenado y la memoria es limitada.
def twoSumSorted(numbers, target):
lo, hi = 0, len(numbers) - 1
while lo < hi:
s = numbers[lo] + numbers[hi]
if s == target:
return [lo + 1, hi + 1] # 1-indexed as per LeetCode 167
elif s < target:
lo += 1
else:
hi -= 1
return []
print(twoSumSorted([2, 7, 11, 15], 9)) # [1, 2]
print(twoSumSorted([2, 3, 4], 6)) # [1, 3]
print(twoSumSorted([-1, 0], -1)) # [1, 2]Three-Sum (LeetCode 15)
LeetCode 15 «Three Sum»: encuentre todas las tripletas únicas cuya suma sea cero. Ordene el array, fije un elemento cada vez y aplique la técnica de dos punteros al subarray ordenado restante. Omita los valores duplicados para evitar tripletas repetidas. Tiempo: O(n²), que es óptimo para este problema, ya que la propia salida puede contener O(n²) tripletas.
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: # skip duplicates
continue
lo, hi = i + 1, len(nums) - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if s == 0:
result.append([nums[i], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < 0:
lo += 1
else:
hi -= 1
return result
print(threeSum([-1, 0, 1, 2, -1, -4])) # [[-1,-1,2],[-1,0,1]]
print(threeSum([0, 0, 0, 0])) # [[0,0,0]]Four-Sum (LeetCode 18)
LeetCode 18 «Four Sum»: encuentre todas las cuádruplas únicas cuya suma sea target. Extienda Three-Sum: fije dos elementos con dos bucles anidados (omitiendo duplicados) y, después, aplique dos punteros al subarray interior. Tiempo: O(n³). Para k-sum en general, el patrón consiste en aplicar recursión k-2 veces y después dos punteros, lo que da un tiempo de O(n^(k-1)).
def fourSum(nums, target):
nums.sort()
n, result = len(nums), []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1, n-2):
if j > i+1 and nums[j] == nums[j-1]:
continue
lo, hi = j+1, n-1
while lo < hi:
s = nums[i]+nums[j]+nums[lo]+nums[hi]
if s == target:
result.append([nums[i],nums[j],nums[lo],nums[hi]])
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target: lo += 1
else: hi -= 1
return result
print(fourSum([1,0,-1,0,-2,2], 0))
# [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]Two-Sum más cercano a target
Una variante habitual consiste en encontrar el par cuya suma esté más cerca de target (no tiene que ser exactamente igual). Ordene el array y utilice dos punteros. Lleve el seguimiento de la suma más cercana encontrada hasta el momento y actualícela cada vez que encuentre un par con una diferencia absoluta menor respecto a target. Este enfoque O(n log n) es sencillo después de ordenar.
def twoSumClosest(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
best = float('inf')
best_pair = None
while lo < hi:
s = nums[lo] + nums[hi]
if abs(s - target) < abs(best - target):
best = s
best_pair = (nums[lo], nums[hi])
if s < target:
lo += 1
elif s > target:
hi -= 1
else:
return best_pair # exact match
return best_pair
print(twoSumClosest([1, 3, 4, 7, 10], 15)) # (7, 10) => 17, closest to 15
print(twoSumClosest([2, 5, 8, 11], 10)) # (2, 8) => 10, exact!Two-Sum con varios pares (todos los pares)
Para encontrar todos los pares cuya suma sea target, ordene el array y utilice dos punteros, recopilando todos los pares. Después de encontrar un par válido, omita los duplicados desde ambos extremos antes de continuar. Esto requiere O(n log n) para ordenar más O(n) para recorrer el array, es decir, O(n log n) en total. También es válido utilizar un mapa hash para recopilar los pares, pero se debe prestar atención a los duplicados.
def twoSumAllPairs(nums, target):
nums.sort()
lo, hi = 0, len(nums) - 1
pairs = []
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
pairs.append((nums[lo], nums[hi]))
while lo < hi and nums[lo] == nums[lo+1]: lo += 1
while lo < hi and nums[hi] == nums[hi-1]: hi -= 1
lo += 1; hi -= 1
elif s < target:
lo += 1
else:
hi -= 1
return pairs
print(twoSumAllPairs([1,1,2,3,4,4,5], 5)) # [(1,4),(1,4)-deduped,(2,3)]
# After duplicate-skipping: [(1,4),(2,3)]Contar pares cuya suma sea menor que K
Otra variante consiste en contar cuántos pares tienen una suma menor que k. Ordene el array y utilice dos punteros. Cuando nums[lo] + nums[hi] < k, todos los pares (lo, lo+1), (lo, lo+2), ..., (lo, hi) son válidos; es decir, hay hi - lo pares. Avance lo. De lo contrario, reduzca hi. Tiempo total: O(n log n) para ordenar más O(n) para contar.
def countPairsLessThan(nums, k):
nums.sort()
lo, hi = 0, len(nums) - 1
count = 0
while lo < hi:
if nums[lo] + nums[hi] < k:
count += hi - lo # all (lo, lo+1)...(lo, hi) are valid
lo += 1
else:
hi -= 1
return count
print(countPairsLessThan([1, 3, 7, 11, 12], 10)) # (1,3),(1,7),(3,7) => 3
print(countPairsLessThan([3, 5, 2, 3], 7)) # (2,3),(2,3) => 2... verifyTwo-Sum con un mapa hash: gestión de duplicados
Cuando un mismo valor puede aparecer varias veces y necesita contar los pares válidos (no solo comprobar si existen), almacene las frecuencias en el mapa. Para los pares cuyos dos elementos son iguales, el número de pares que se obtiene a partir de una frecuencia f es f*(f-1)//2. Para los pares cuyos dos elementos son distintos, multiplique sus frecuencias. Esto permite contar todos los pares válidos en O(n).
from collections import Counter
def countTwoSumPairs(nums, target):
freq = Counter(nums)
count = 0
seen = set()
for x in freq:
y = target - x
if y in freq and (x, y) not in seen:
if x == y:
count += freq[x] * (freq[x] - 1) // 2
else:
count += freq[x] * freq[y]
seen.add((x, y))
seen.add((y, x))
return count
print(countTwoSumPairs([1,1,2,3,4,4,3], 4))
# Pairs summing to 4: (1,3)x2x2=4, (0+more)...Reconocer las variantes del patrón Two-Sum
El patrón two-sum aparece con muchas formas diferentes. Reconózcalo cuando un problema pida encontrar dos o más elementos que satisfagan una relación numérica (suma, producto o diferencia). La estrategia fundamental es siempre la misma: fijar un elemento y buscar su complemento en una estructura precalculada (un mapa hash o un array ordenado más un puntero). Extiéndalo a k-sum fijando k-2 elementos con bucles anidados y aplicando el caso base.
# Summary of approaches by scenario
scenarios = [
('Unsorted array, any indices, one pair', 'hash map O(n) time O(n) space'),
('Sorted array, any indices, one pair', 'two pointers O(n) time O(1) space'),
('All unique pairs summing to target', 'sort + two pointers O(n log n)'),
('Three numbers summing to zero (3-sum)', 'sort + fix + two pointers O(n^2)'),
('k numbers summing to target (k-sum)', 'sort + k-2 loops + two pointers O(n^(k-1))')
]
for scenario, approach in scenarios:
print(f'{scenario}\n => {approach}\n')Comunicación en entrevistas para Two-Sum
Cuando aparezca two-sum en una entrevista, explique su razonamiento en voz alta: «Necesito dos números cuya suma sea target. Para cada número x, debo comprobar si existe target-x. Puedo responder a eso en O(1) con un mapa hash, lo que da un tiempo total de O(n) y un espacio de O(n). Como alternativa, si el array estuviera ordenado, podría utilizar dos punteros con un espacio de O(1)». Exponga ambos enfoques y pregunte si existen restricciones de espacio antes de elegir.
Comprobación rápida
Ponga a prueba su comprensión de los conceptos de Data Structures & Algorithms — Coding Interview Prep de esta lección.
Repaso de la lección
En esta lección aprendió que: two-sum utiliza una tabla hash para comprobar si existe el complemento en O(1), lo que da un coste total de O(n), en arreglos ordenados, dos punteros logran un espacio de O(1), y three-sum y four-sum se reducen a two-sum mediante ordenamiento y bucles anidados, con costes de O(n²) y O(n³), respectivamente. A continuación exploraremos patrones de conteo de frecuencias y agrupación con defaultdict y Counter.
Preguntas frecuentes
¿La lección «Two-sum y sus numerosas variantes» es gratis?
Sí — el texto completo de «Two-sum y sus numerosas variantes» es gratis para leer aquí en la web. Para practicarla de forma interactiva (editor de código integrado y tutor de IA 24/7) y desbloquear el resto del curso de DSA Interview Prep, actualiza a CoddyKit PRO. El curso de DSA Interview Prep incluye 4 lecciones en total.
¿Qué aprenderé en «Two-sum y sus numerosas variantes»?
Resuelva two-sum, three-sum, four-sum y two-sum with sorted array usando mapas hash y dos punteros, y compare los costes temporales y espaciales. Practicas DSA Interview Prep con código real que ejecutas directamente en el navegador, y un tutor de IA 24/7 responde tus preguntas mientras trabajas en la lección.
¿Necesito experiencia previa para empezar DSA Interview Prep?
No se requiere experiencia previa. DSA Interview Prep en CoddyKit está estructurado para principiantes hasta estudiantes avanzados, así que puedes empezar aquí o desde el inicio y avanzar a tu ritmo. Esta es la lección 2 de 4.
¿Cuánto tiempo toma la lección «Two-sum y sus numerosas variantes»?
La mayoría de las lecciones de CoddyKit toman alrededor de 5–10 minutos. Cada una es compacta e interactiva, así que avanzas constantemente y retomas exactamente por donde dejaste en la web y la app.
¿Puedo escribir y ejecutar código en esta lección de DSA Interview Prep?
Sí. Cada lección de DSA Interview Prep incluye un editor de código integrado, así que escribes y ejecutas código real directamente en tu navegador y obtienes retroalimentación instantánea de IA — sin configuración local necesaria.
Todas las lecciones de este curso
- Internals de las funciones hash y gestión de colisiones
- Two-sum y sus numerosas variantes
- Conteo y agrupación por frecuencia
- Secuencia consecutiva más larga y caché LRU