Farkı k olan çiftleri say
Görev tanımı
Problem
Bir fiyatlandırma ekibi bir listedeki kaç farklı fiyat çiftinin tam olarak k kadar farklı olduğunu bilmek istiyor. Bir nums tam sayı listesi ve bir k ≥ 0 tam sayısı verildiğinde, ikisi de listede bulunan, a ≤ b ve b - a = k olan farklı (a, b) değer çiftlerinin sayısını döndür. k = 0 olan bir çift, değerin en az iki kez görünmesini gerektirir. Listede en fazla 10.000 değer var, bu yüzden diğer her değerle değil, bir arama tablosuyla karşılaştır.
Örnekler
Input: nums = [3, 1, 4, 1, 5], k = 2
Output: 2
Neden: (1, 3) ve (3, 5); ikinci 1 yeni bir çift oluşturmaz
Input: nums = [1, 2, 3, 4, 5], k = 1
Output: 4
Input: nums = [1, 3, 1, 5, 4], k = 0
Output: 1
Neden: edge case: yalnız 1 iki kez görünüyor
İpuçları
0 / 3
Tekrarlar yalnız k 0 olduğunda önemli. Başka herhangi bir k için her farklı değer en fazla bir çift başlatabilir.
Bir a değeri için bir çifti tamamlayabilecek tek eş a + k'dir; tıpkı Two Sum'da x'in tek eşinin target - x olması gibi.
Değerleri bir kez say. k > 0 için a + k'si de bulunan farklı a değerlerini say; k = 0 için birden fazla kez görülen değerleri say.
- Hedef zaman
- O(n)
- Hedef alan
- O(n)
Kısıtlar
- k ≥ 0
- nums.length ≤ 10⁴
Çözüm
Çiftler farklı değerlere göre sayılır, bu yüzden liste önce bir değer sayıları tablosuna indirilir. k pozitifken her farklı a değeri yalnız a + k ile eşleşebilir ve tabloda tek bir arama bunu cevaplar; böylece eşi var olan değerleri saymak her çifti küçük ucundan tam bir kez sayar. k 0 olduğunda eş değerin kendisidir; yani çift tam olarak o değer en az iki kez göründüğünde vardır. Tabloyu kurmak da taramak da doğrusaldır; zaman ve alan 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)) # -> 1Kodda değil de fikirde mi takıldın? Two Sum bunu anlatıyor.