Скачать или смотреть Leetcode [220] Contains Duplicate III

https://leetcode.com/problems/contain...

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Discord:   / discord  

This one of find duplicates form of question, with some constraints added (and a bit relaxed). The dupes must be near each other (within 'k'), and they dont have to be "exact" duplicates - almost duplicate is fine (diff of at most 't').

Solution 1 (Brute Force): You can use a simple Brute Force Solution, where run through the entire array, check both conditions. Technically n^2, but you can limit the inner loop based on the nearby condition. This will be O(nk), but worst case will devolve to n^2 (if k is large enough).

Solution 2 (Sorted Approach): You can use an aux data structure like a BST or a Treemap to keep the elements in sorted order. Also keep a reverse lookup to track the index of the value.
Time complexity: O ( n * log n), and Space complexity: O(n). You can limit the sorted structure to only store the k elements in the active window. This will reduce the Time complexity to O (nlogk) and Space complexity to O(k).

Solution 3 (Buckets): You can use a combination of sliding window and bucketing. Use an aux structure to store elements in t+1 sized buckets. You will only be tracking the trailing k elements. If the bucket for current element already contains an element, then we have a match. There may be a potential match with adjacent buckets too, so check the values in the three buckets (current, pervious and next).

Love questions such as these that have multiple solutions. As you watch the video (and practice this question) focus on learning the concepts.