Two Sum II: Sorted Input

Q: ¿Por qué funcionan dos punteros para Two Sum en un arreglo ordenado?

Cuando la suma de los dos extremos es demasiado pequeña, el valor de la izquierda es demasiado pequeño para todos los valores que aún pueden emparejarse con él, porque el extremo derecho es el mayor de ellos. Puedes descartarlo definitivamente. El mismo razonamiento permite descartar el valor de la derecha cuando la suma es demasiado grande. El par que es la respuesta nunca se descarta, así que los punteros terminan en él.

Q: ¿Cuál es la complejidad temporal de Two Sum II?

La solución con dos punteros se ejecuta en tiempo O(n) y usa O(1) espacio adicional: en cada paso, un puntero se mueve hacia adentro, y se encuentran después de como máximo n-1 pasos. Buscar cada complemento mediante búsqueda binaria toma O(n log n) , y comprobar cada par toma O(n²) .

Q: ¿Por qué no usar un mapa hash como en el primer Two Sum?

Un mapa hash funciona y también se ejecuta en tiempo O(n) , pero almacena hasta n valores. El ordenamiento hace innecesaria esa memoria: los dos punteros saben en qué dirección avanzar basándose únicamente en la suma. Los entrevistadores hacen esta pregunta para ver si aprovechas el orden que te dieron.

Q: ¿Cuándo es mejor opción la búsqueda binaria aquí?

Cuando un valor es fijo y solo necesitas su pareja. Si numbers[0] debe estar en el par, una búsqueda binaria encuentra el otro índice en O(log n) . Para encontrar un par desconocido, el recorrido con dos punteros es más rápido que n búsquedas independientes.

FácilDos punteros Búsqueda binaria

+10

Recibes un arreglo de números enteros numbers ordenado en orden no decreciente y un entero target. Exactamente un par de posiciones distintas contiene dos valores que suman target. Devuelve esas dos posiciones como índices basados en 0, primero el índice menor.

Función

twoSumSorted(numbers: integer-array, target: integer) → integer-array

numbersinteger-array: el arreglo ordenado de números enteros
targetinteger: la suma que deben alcanzar los dos valores
Devuelveinteger-array: los dos índices basados en 0 [i, j] con i < j y numbers[i] + numbers[j] == target

Restricciones

2 ≤ numbers.length ≤ 10⁴
-5 × 10⁸ ≤ numbers[i] ≤ 5 × 10⁸
-10⁹ ≤ target ≤ 10⁹
numbers está ordenado en orden no decreciente.
Exactamente un par de índices i < j cumple numbers[i] + numbers[j] == target.

Ejemplos

Entrada: numbers = [-4, 1, 3, 8, 12]target = 9
Salida: [1, 3]
Explicación: 1 está en el índice 1 y 8 en el índice 3, y 1 + 8 = 9. Ningún otro par suma 9: por ejemplo, -4 + 12 = 8.

+13 pruebas ocultas al enviar

Para ir más allá

¿Puedes resolverlo en tiempo O(n) con memoria adicional O(1)?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Un mapa hash resuelve la versión sin ordenar en una sola pasada, pero requiere O(n) de memoria. Aquí el arreglo está ordenado, y ese orden te indica hacia dónde moverte. Coloca un puntero en cada extremo. Si la suma es demasiado pequeña, solo un valor mayor a la izquierda puede ayudar; si es demasiado grande, solo puede ayudar un valor menor a la derecha. Cada paso descarta definitivamente un valor, así que una sola pasada encuentra el par sin memoria adicional.

Comprueba cada par

Correcto, pero no termina con las pruebas más grandes

Intuición

Prueba cada par de posiciones i < j y comprueba si numbers[i] + numbers[j] es igual a target. Como i avanza desde la izquierda y j empieza justo después, el primer par que encuentres ya tendrá primero el índice menor.

Esto es correcto, pero ignora el orden de clasificación. Con n = 10^4 hay alrededor de 5 × 10^7 pares y, cuando la respuesta está cerca del final del arreglo, pruebas casi todos. Eso es demasiado lento para las pruebas grandes.

Algoritmo

Recorre con un bucle i todos los índices.
Recorre con un bucle j desde i+1 hasta el último índice.
Si numbers[i] + numbers[j] es igual a target, devuelve [i, j].

def twoSumSorted(numbers, target):
    n = len(numbers)
    for i in range(n):
        for j in range(i + 1, n):
            if numbers[i] + numbers[j] == target:
                return [i, j]
    return []

Búsqueda binaria para cada compañero

Intuición

Una vez que fijas el primer valor numbers[i], conoces exactamente su complemento: target - numbers[i]. La parte del arreglo a la derecha de i está ordenada, así que la búsqueda binaria puede indicar en O(log n) pasos si ese complemento está allí.

Para [-4, 1, 3, 8, 12] y target = 9: en i = 0, el complemento sería 13, que no aparece. En i = 1, el complemento es 8, y la búsqueda lo encuentra en el índice 3. La respuesta es [1, 3].

Buscar solo a la derecha de i mantiene primero el índice menor e impide que un valor se empareje consigo mismo. El par es único, así que el valor complementario aparece como máximo una vez en ese rango y cualquier coincidencia es la respuesta. En total: n búsquedas de O(log n) cada una.

Algoritmo

Recorre i desde 0 hasta n-2.
Calcula need = target - numbers[i].
Busca need mediante búsqueda binaria entre los índices i+1 y n-1.
Si lo encuentras en mid, devuelve [i, mid].

def twoSumSorted(numbers, target):
    n = len(numbers)
    for i in range(n - 1):
        need = target - numbers[i]
        lo, hi = i + 1, n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if numbers[mid] == need:
                return [i, mid]
            if numbers[mid] < need:
                lo = mid + 1
            else:
                hi = mid - 1
    return []

Dos punteros desde ambos extremos

Intuición

Empieza con left = 0 y right = n-1 y observa numbers[left] + numbers[right]. Si es igual a target, has terminado. Si es demasiado pequeño, numbers[left] no puede formar parte de la respuesta: incluso emparejado con el valor más grande que aún está en juego, no alcanza. Así que mueve left hacia la derecha. Si la suma es demasiado grande, numbers[right] tampoco puede formar parte, ya que incluso el elemento más pequeño que queda como pareja hace que la suma se pase. Así que mueve right hacia la izquierda.

Cada movimiento descarta un valor que nunca puede formar parte del par, y el par en sí nunca se descarta. Los punteros se encuentran después de como máximo n-1 movimientos, así que el recorrido es O(n) y usa dos variables.

Con [-4, 1, 3, 8, 12] y target = 9: -4 + 12 = 8 es demasiado pequeño, así que left se mueve al índice 1. Después, 1 + 12 = 13 es demasiado grande, así que right se mueve al índice 3. Ahora 1 + 8 = 9, y la respuesta es [1, 3].

Algoritmo

Establece left en 0 y right en n-1.
Mientras left < right, calcula total = numbers[left] + numbers[right].
Si total es igual a target, devuelve [left, right].
Si total es menor, suma 1 a left; si es mayor, resta 1 a right.

def twoSumSorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1  # need a bigger sum
        else:
            right -= 1  # need a smaller sum
    return []

Errores comunes y casos límite

El bucle de dos punteros es corto, así que los errores se esconden en los detalles que lo rodean.

Devolver posiciones basadas en 1. Esta versión necesita índices basados en 0: para [-4, 1, 3, 8, 12] y target = 9, la respuesta es [1, 3], no [2, 4]. En Lua y R, resta 1 antes de devolver el resultado.
Usar un bucle con left <= right. Cuando los punteros se encuentran, la suma usaría dos veces el mismo valor.
Mover el puntero equivocado. Una suma demasiado pequeña necesita un valor mayor, y solo left puede proporcionarlo.
Rechazar valores duplicados. Con [2, 2, 5, 7] y target = 4, se usan ambos 2, que están en posiciones diferentes.
Desbordamiento. Los límites en este caso mantienen todas las sumas dentro del rango de un entero de 32 bits. Si los valores pudieran llegar a 10^9, súmalos usando un tipo de 64 bits.

Preguntas frecuentes4

¿Por qué funcionan dos punteros para Two Sum en un arreglo ordenado?

Cuando la suma de los dos extremos es demasiado pequeña, el valor de la izquierda es demasiado pequeño para todos los valores que aún pueden emparejarse con él, porque el extremo derecho es el mayor de ellos. Puedes descartarlo definitivamente. El mismo razonamiento permite descartar el valor de la derecha cuando la suma es demasiado grande. El par que es la respuesta nunca se descarta, así que los punteros terminan en él.

¿Cuál es la complejidad temporal de Two Sum II?

La solución con dos punteros se ejecuta en tiempo O(n) y usa O(1) espacio adicional: en cada paso, un puntero se mueve hacia adentro, y se encuentran después de como máximo n-1 pasos. Buscar cada complemento mediante búsqueda binaria toma O(n log n), y comprobar cada par toma O(n²).

¿Por qué no usar un mapa hash como en el primer Two Sum?

Un mapa hash funciona y también se ejecuta en tiempo O(n), pero almacena hasta n valores. El ordenamiento hace innecesaria esa memoria: los dos punteros saben en qué dirección avanzar basándose únicamente en la suma. Los entrevistadores hacen esta pregunta para ver si aprovechas el orden que te dieron.

¿Cuándo es mejor opción la búsqueda binaria aquí?

Cuando un valor es fijo y solo necesitas su pareja. Si numbers[0] debe estar en el par, una búsqueda binaria encuentra el otro índice en O(log n). Para encontrar un par desconocido, el recorrido con dos punteros es más rápido que n búsquedas independientes.

Python

def twoSumSorted(numbers, target):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

numbers = [-4, 1, 3, 8, 12]
target = 9

Esperado

[1, 3]

Two Sum II: Sorted Input

Función

Restricciones

Ejemplos

Pistas

Solución

Comprueba cada par

Búsqueda binaria para cada compañero

Dos punteros desde ambos extremos

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares