220. Contains Duplicate III
1. Description
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.
2. Example
Example 1:
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
3. Constraints
- 0 <= nums.length <= $2 * 10^4$
- $-2^{31}$ <= nums[i] <= $2^{31} - 1$
- 0 <= k <= $10^4$
- 0 <= t <= $2^{31} - 1$
4. Solutions
My Accepted Solution
n = i_nums.size()
Time complexity: O($nlog_2k$)
Space complexity: O(k)
class Solution
{
public:
bool containsNearbyAlmostDuplicate(const vector<int> &i_nums, int k, int t)
{
multiset<long> window; // maintain a slide window of size k
for(int i = 0; i < i_nums.size(); i++)
{
if(i > k) // this means the size of the window exceeds k, so we need to remove the prior item
{
window.erase(window.find(i_nums[i - k - 1]));
}
auto iter = window.insert(i_nums[i]);
// then, we check both sides neighbors to find wheher or not they match the condition
// since they are the nearest value for the current value
// so they are more likely to match the conditon
if(iter != begin(window) && *iter - *prev(iter) <= t)
return true;
if(next(iter) != window.end() && *next(iter) - *iter <= t)
return true;
}
return false;
}
};