Задача: 220. Contains Duplicate III
Сложность: hard

Вам дан массив целых чисел nums и два целых числа indexDiff и valueDiff.

Найдите пару индексов (i, j) таких, что:
i != j,
abs(i - j) <= indexDiff,
abs(nums[i] - nums[j]) <= valueDiff.

Верните true, если такая пара существует, или false в противном случае.

Пример:

Input: nums = [1,2,3,1], indexDiff = 3, valueDiff = 0
Output: true
Explanation: We can choose (i, j) = (0, 3).
We satisfy the three conditions:
i != j --> 0 != 3
abs(i - j) <= indexDiff --> abs(0 - 3) <= 3
abs(nums[i] - nums[j]) <= valueDiff --> abs(1 - 1) <= 0

👨‍💻 Алгоритм:

1️⃣Инициализация и вычисление корзин:
Рассчитать ширину корзины w = t + 1. Инициализировать пустой хэш-таблицей buckets. Определить функцию getID, которая возвращает идентификатор корзины для элемента x и ширины корзины w.

2️⃣Итерация и проверка корзин:
Перебрать все элементы массива nums. Для каждого элемента nums[i]: Определить его корзину с помощью getID. Проверить, есть ли в текущей корзине элемент. Если есть, вернуть true. Проверить соседние корзины на наличие "почти дубликатов". Если есть, вернуть true. Если текущая корзина пуста и в соседних корзинах нет "почти дубликатов", добавить текущий элемент в соответствующую корзину. Если текущий индекс превышает k, удалить элемент из корзины, которая вышла за пределы окна.

3️⃣Завершение:
Если ни одна пара "почти дубликатов" не найдена, вернуть false.

😎 Решение:

class Solution:
    def containsNearbyAlmostDuplicate(self, nums, k, t):
        if t < 0: return False
        buckets = {}
        w = t + 1

        for i in range(len(nums)):
            bucket = nums[i] // w if nums[i] >= 0 else (nums[i] + 1) // w - 1
            if bucket in buckets: return True
            if bucket - 1 in buckets and abs(nums[i] - buckets[bucket - 1]) < w: return True
            if bucket + 1 in buckets and abs(nums[i] - buckets[bucket + 1]) < w: return True
            buckets[bucket] = nums[i]
            if i >= k:
                del buckets[nums[i - k] // w if nums[i - k] >= 0 else (nums[i - k] + 1) // w - 1]
        return False

Ставь 👍 и забирай 📚 Базу знаний