Saltar al contenido

Dos punteros

Lección 2 de 14 · 5 min

Dos punteros

Paso 1 de 9

El array está ordenado, así que empieza lo más abierto posible: un puntero en cada extremo.

La idea

Mantén un índice en cada extremo y muévelos uno hacia el otro según lo que veas. Cada paso descarta de una vez todo un grupo de pares. La fuerza bruta revisa cada par en O(n²); la técnica de dos punteros (two pointers) hace el mismo trabajo en O(n).

Ejemplo del mundo real

Dos personas buscan un par de tomos que combinen en un librero largo: cada una empieza por un extremo y avanza hacia el centro. Se encuentran a la mitad después de recorrer el estante exactamente una vez, en lugar de que una de ellas lo vuelva a recorrer por cada libro.

El código

Te toca

¿Qué imprime esto?

nums = [2, 5, 9]
l, r = 0, 2
while l < r:
  print(nums[l] + nums[r])
  l += 1
  r -= 1

Mini quiz

1 / 3

Con una entrada ordenada, dos punteros convierten una búsqueda de pares O(n²) en: