หาคู่ที่แตกต่างกันทั้งหมดที่มีความต่างเท่ากับ k ใน Python

นับ Distinct Pairs ที่มีความต่างเท่ากับ k

กำหนดลิสต์ตัวเลขและ k หาจำนวนคู่ (a,b) ที่ |a-b| = k (นับคู่ที่ต่างกัน ไม่สนใจลำดับ)

วิธีที่ 1: Two Loops O(N²)

lst = [5,3,7,2,9]
k = 2
count = 0
for i in range(len(lst)):
    for j in range(i+1, len(lst)):
        if abs(lst[i]-lst[j]) == k:
            count += 1
print(count)  # 3

วิธีที่ 2: Two Pointers หลัง Sort O(N log N)

lst = [5,3,7,2,9]
k = 2
lst.sort()
i = j = 0
count = 0
while i < len(lst) and j < len(lst):
    diff = lst[i] - lst[j]
    if diff == k:
        count += 1; i += 1; j += 1
    elif diff > k:
        j += 1
    else:
        i += 1
print(count)  # 3