Saltar al contenido

Contar pares con una diferencia dada

Fácil#hash-map#complement-lookup~15 min

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

Tiempo objetivo
O(n)
Espacio objetivo
O(n)

Restricciones

  • k ≥ 0
  • nums.length ≤ 10⁴

¿Lo que te frena es la idea y no el código? Two Sum lo explica.

Python 3Ctrl+Enter ejecuta
Caso de prueba propio