← Static tasks

220. Contains Duplicate III

leetcode hard

#array#csharp#hard#hash-table#leetcode#math#sliding-window

Task

Вам дан массив целых чисел 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

C# solution

matched/original
public class Solution {
    public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (t < 0) return false;
        Dictionary<long, long> buckets = new Dictionary<long, long>();
        long w = (long)t + 1;
        for (int i = 0; i < nums.Length; i++) {
            long bucket = GetID(nums[i], w);
            if (buckets.ContainsKey(bucket)) return true;
            if (buckets.ContainsKey(bucket - 1) && Math.Abs(nums[i] - buckets[bucket - 1]) < w) return true;
            if (buckets.ContainsKey(bucket + 1) && Math.Abs(nums[i] - buckets[bucket + 1]) < w) return true;
            buckets[bucket] = nums[i];
            if (i >= k) {
                buckets.Remove(GetID(nums[i - k], w));
            }
        }
        return false;
    }
    private long GetID(long x, long w) {
        return x < 0 ? (x + 1) / w - 1 : x / w;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool ContainsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if (t < 0) return false;
        unordered_map<long, long> buckets = new unordered_map<long, long>();
        long w = (long)t + 1;
        for (int i = 0; i < nums.size(); i++) {
            long bucket = GetID(nums[i], w);
            if (buckets.count(bucket)) return true;
            if (buckets.count(bucket - 1) && abs(nums[i] - buckets[bucket - 1]) < w) return true;
            if (buckets.count(bucket + 1) && abs(nums[i] - buckets[bucket + 1]) < w) return true;
            buckets[bucket] = nums[i];
            if (i >= k) {
                buckets.Remove(GetID(nums[i - k], w));
            }
        }
        return false;
    }
    private long GetID(long x, long w) {
        return x < 0 ? (x + 1) / w - 1 : x / w;
    }
}

Java solution

matched/original
class Solution {
    private long getID(long x, long w) {
        return Math.floorDiv(x, w);
    }

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (t < 0) return false;
        Map<Long, Long> buckets = new HashMap<>();
        long w = (long) t + 1;
        for (int i = 0; i < nums.length; ++i) {
            long bucket = getID(nums[i], w);
            if (buckets.containsKey(bucket)) return true;
            if (
                buckets.containsKey(bucket - 1) &&
                Math.abs(nums[i] - buckets.get(bucket - 1)) < w
            ) return true;
            if (
                buckets.containsKey(bucket + 1) &&
                Math.abs(nums[i] - buckets.get(bucket + 1)) < w
            ) return true;
            buckets.put(bucket, (long) nums[i]);
            if (i >= k) buckets.remove(getID(nums[i - k], w));
        }
        return false;
    }
}

JavaScript solution

matched/original
function getID(x, w) {
    return x < 0 ? Math.floor((x + 1) / w) - 1 : Math.floor(x / w);
}

var containsNearbyAlmostDuplicate = function(nums, k, t) {
    if (t < 0) return false;
    const buckets = new Map();
    const w = t + 1;

    for (let i = 0; i < nums.length; i++) {
        const bucket = getID(nums[i], w);
        if (buckets.has(bucket)) return true;
        if (buckets.has(bucket - 1) && Math.abs(nums[i] - buckets.get(bucket - 1)) < w) return true;
        if (buckets.has(bucket + 1) && Math.abs(nums[i] - buckets.get(bucket + 1)) < w) return true;
        buckets.set(bucket, nums[i]);
        if (i >= k) {
            buckets.delete(getID(nums[i - k], w));
        }
    }
    return false;
};

Python solution

matched/original
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

Go solution

matched/original
func getID(x, w int) int {
    if x < 0 {
        return (x + 1) / w - 1
    }
    return x / w
}

func containsNearbyAlmostDuplicate(nums []int, k int, t int) bool {
    if t < 0 {
        return false
    }
    buckets := make(map[int]int)
    w := t + 1

    for i, num := range nums {
        bucket := getID(num, w)
        if _, ok := buckets[bucket]; ok {
            return true
        }
        if val, ok := buckets[bucket-1]; ok && abs(num-val) < w {
            return true
        }
        if val, ok := buckets[bucket+1]; ok && abs(num-val) < w {
            return true
        }
        buckets[bucket] = num
        if i >= k {
            delete(buckets, getID(nums[i-k], w))
        }
    }
    return false
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Explanation

Algorithm

1️⃣

Инициализация и вычисление корзин:

Рассчитать ширину корзины w = t + 1.

Инициализировать пустой хэш-таблицей buckets.

Определить функцию getID, которая возвращает идентификатор корзины для элемента x и ширины корзины w.

2️⃣

Итерация и проверка корзин:

Перебрать все элементы массива nums.

Для каждого элемента nums[i]:

Определить его корзину с помощью getID.

Проверить, есть ли в текущей корзине элемент. Если есть, вернуть true.

Проверить соседние корзины на наличие "почти дубликатов". Если есть, вернуть true.

Если текущая корзина пуста и в соседних корзинах нет "почти дубликатов", добавить текущий элемент в соответствующую корзину.

Если текущий индекс превышает k, удалить элемент из корзины, которая вышла за пределы окна.

3️⃣

Завершение:

Если ни одна пара "почти дубликатов" не найдена, вернуть false.

😎