Contar pares con una diferencia dada
La misión
Problema
Un equipo de precios quiere saber cuántos pares distintos de precios de una lista difieren exactamente en k. Dada una lista de enteros nums y un entero k ≥ 0, devuelve la cantidad de pares distintos de valores (a, b) con a ≤ b, ambos presentes en la lista, y b - a = k. Un par con k = 0 necesita que el valor aparezca al menos dos veces. La lista tiene hasta 10 000 valores, así que compara contra una tabla de consulta en lugar de contra cada uno de los demás valores.
Ejemplos
Input: nums = [3, 1, 4, 1, 5], k = 2
Output: 2
Por qué: (1, 3) y (3, 5); el segundo 1 no forma un par nuevo
Input: nums = [1, 2, 3, 4, 5], k = 1
Output: 4
Input: nums = [1, 3, 1, 5, 4], k = 0
Output: 1
Por qué: caso límite: solo el 1 aparece dos veces
Pistas
0 / 3
Los duplicados solo importan cuando k es 0. Para cualquier otro k, cada valor distinto puede iniciar como máximo un par.
Para un valor a, el único compañero que puede completar un par es a + k, igual que en Two Sum el único compañero de x es target - x.
Cuenta los valores una vez. Para k > 0, cuenta los valores distintos a cuyo a + k también está presente; para k = 0, cuenta los valores que aparecen más de una vez.
- Tiempo objetivo
- O(n)
- Espacio objetivo
- O(n)
Restricciones
- k ≥ 0
- nums.length ≤ 10⁴
Solución
Los pares se cuentan por valores distintos, así que primero la lista se reduce a una tabla con el conteo de cada valor. Cuando k es positivo, cada valor distinto a solo puede emparejarse con a + k, y una sola búsqueda en la tabla lo responde, así que contar los valores cuyo compañero existe cuenta cada par exactamente una vez, desde su extremo menor. Cuando k es 0, el compañero es el propio valor, así que el par existe exactamente cuando ese valor aparece al menos dos veces. Construir la tabla y recorrerla son operaciones lineales, así que el tiempo y el espacio son O(n).
from collections import Counter
def gap_pairs(nums, k):
counts = Counter(nums)
if k == 0:
return sum(1 for c in counts.values() if c > 1) # a value paired with itself
return sum(1 for a in counts if a + k in counts) # counted from the smaller end
print(gap_pairs([3, 1, 4, 1, 5], 2)) # -> 2
print(gap_pairs([1, 2, 3, 4, 5], 1)) # -> 4
print(gap_pairs([1, 3, 1, 5, 4], 0)) # -> 1¿Lo que te frena es la idea y no el código? Two Sum lo explica.