Dos punteros, sin tabla
Por qué importa "Encuentra dos cosas que sumen X" tiene una respuesta famosa: mételo todo en un conjunto y busca la pareja. Es rápida, y necesita una copia de todos los datos. Cuando los datos están ordenados, casi no necesitas memoria.
Un servicio de regalos vende lotes de dos productos distintos por un precio de lote fijo. La lista de precios de productos está ordenada, no tiene repetidos y está en un dispositivo integrado con muy poca memoria libre. Para un precio de lote, necesitas el número de parejas de productos cuyos precios suman exactamente ese precio.
prices = [1, 2, 3, 4, 5, 6] # sorted, no repeats
count_pairs(Tape(prices), 7) # 3: (1, 6), (2, 5), (3, 4)Escribe count_pairs(tape, target). tape es una Tape de precios enteros, ordenados de menor a mayor, sin repetidos. Devuelve cuántas parejas de dos elementos distintos suman exactamente target (cada pareja contada una vez). Presupuestos: para 20,000 elementos lee como mucho 60,000 valores, y usa como mucho 16,000 bytes de memoria de trabajo mientras corre tu función (medido con tracemalloc; un conjunto o una lista de los 20,000 precios pasa de 150,000 bytes). len(tape) es gratis.
¿Has visto un problema en esta lección? Avísanos · Preguntar sobre esta lección
Este ejercicio se abre pronto
Termina la lección anterior y esta se desbloquea. Todo el curso es gratis, no hace falta cuenta, y puedes leer esta lección ahora mismo.
Este navegador está bloqueando las cookies de learn.floati.life, así que las lecciones que terminaste aquí no se pueden abrir en orden. Permite las cookies de este sitio y recarga.