Pular para o conteúdo

Contar pares com uma diferença dada

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

A missão

Problema

Uma equipe de precificação quer saber quantos pares distintos de preços em uma lista diferem exatamente em k. Dada uma lista de inteiros nums e um inteiro k ≥ 0, retorne o número de pares distintos de valores (a, b) com a ≤ b, ambos presentes na lista, e b - a = k. Um par com k = 0 exige que o valor apareça pelo menos duas vezes. A lista tem até 10.000 valores, então compare com uma tabela de busca em vez de com cada um dos outros valores.

Exemplos

Input:  nums = [3, 1, 4, 1, 5], k = 2
Output: 2
Por quê: (1, 3) e (3, 5); o segundo 1 não forma um par novo
Input:  nums = [1, 2, 3, 4, 5], k = 1
Output: 4
Input:  nums = [1, 3, 1, 5, 4], k = 0
Output: 1
Por quê: edge case: só o 1 aparece duas vezes

Dicas

0 / 3

Tempo-alvo
O(n)
Espaço-alvo
O(n)

Restrições

  • k ≥ 0
  • nums.length ≤ 10⁴

Travou na ideia, e não no código? Two Sum explica isso.

Python 3Ctrl+Enter executa
Caso de teste personalizado