Подсчитать уникальные пары с разницей не меньше k.

1. Подсчитать уникальные пары с разницей не меньше k.

Условие задачи:
Дан массив целых чисел nums и целое число k.
Верните количество уникальныхпар с разницей >= k в массиве.

Пример:

k_pairs([1, 2, 3, 4], 3) -> 1
k_pairs([1, 1, 3, 4], 2) -> 4
k_pairs([], 2) -> 0
k_pairs([1, 1, 3, 4], 20) -> 0

Спойлеры к решению

Подсказки

Судя по примеру k_pairs([1, 1, 3, 4], 2) -> 4, пары считаются по индексам, а не только по уникальным значениям.
То есть два одинаковых числа 1 дают разные пары с 3 и 4.
Нужно посчитать пары (i, j), где i < j и abs(nums[i] - nums[j]) >= k.
Удобно сначала отсортировать массив.
После сортировки можно использовать два указателя.
Для каждого левого элемента ищем первый правый элемент, разница с которым >= k.
Все элементы правее него тоже подходят.

Решение

def k_pairs(nums: list[int], k: int) -> int:
    if len(nums) < 2:
        return 0

    nums = sorted(nums)
    n = len(nums)

    count = 0
    right = 1

    for left in range(n):
        if right <= left:
            right = left + 1

        while right < n and nums[right] - nums[left] < k:
            right += 1

        count += n - right

    return count

Проверка на примерах:

print(k_pairs([1, 2, 3, 4], 3))      # 1
print(k_pairs([1, 1, 3, 4], 2))      # 4
print(k_pairs([], 2))                # 0
print(k_pairs([1, 1, 3, 4], 20))     # 0

Решение сортирует массив и считает количество пар с разницей >= k. После сортировки для каждого элемента nums[left] находится первый элемент nums[right], который отличается от него минимум на k. Все элементы после right тоже подходят, поэтому к ответу добавляется n - right.

Сложность решения: O(n log n) из-за сортировки. Сам проход двумя указателями работает за O(n).