Contar pares com uma diferença dada
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
Duplicados só importam quando k é 0. Para qualquer outro k, cada valor distinto pode começar no máximo um par.
Para um valor a, o único parceiro que pode completar um par é a + k, assim como no Two Sum o único parceiro de x é target - x.
Conte os valores uma vez. Para k > 0, conte os valores distintos a cujo a + k também está presente; para k = 0, conte os valores vistos mais de uma vez.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(n)
Restrições
- k ≥ 0
- nums.length ≤ 10⁴
Solução
Os pares são contados por valores distintos, então a lista é primeiro reduzida a uma tabela de contagens de valores. Quando k é positivo, cada valor distinto a só pode formar par com a + k, e uma única busca na tabela responde a isso; assim, contar os valores cujo parceiro existe conta cada par exatamente uma vez, a partir da sua ponta menor. Quando k é 0, o parceiro é o próprio valor, então o par existe exatamente quando esse valor aparece pelo menos duas vezes. Construir a tabela e varrê-la são operações lineares, então o tempo e o espaço são 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)) # -> 1Travou na ideia, e não no código? Two Sum explica isso.