Cho danh sách số và giá trị k, đếm số cặp phân biệt có hiệu tuyệt đối bằng k.
Cách 1: Hai vòng lặp for (O(n²))
Duyệt mọi cặp (i, j) với i < j, kiểm tra hiệu.
listA = [5, 3, 7, 2, 9]
k = 2
count = 0
for i in range(len(listA)):
for j in range(i+1, len(listA)):
if abs(listA[i] - listA[j]) == k:
count += 1
print("Số cặp:", count) # 3
Cách 2: Sắp xếp + hai con trỏ (Two Pointers)
Sắp xếp mảng, dùng hai chỉ số current_index, next_index di chuyển dựa trên hiệu so với k.
listA = [5, 3, 7, 2, 9]
k = 2
listA.sort()
count = 0
current_index = 0
next_index = 0
while current_index < len(listA):
diff = listA[current_index] - listA[next_index]
if diff == k:
count += 1
next_index += 1
current_index += 1
elif diff > k:
next_index += 1
else:
current_index += 1
print("Số cặp:", count) # 3