### Solutions

This problem is quite classic recently, so here we are trying to shed some light on it and provide some basic solutions to it.

#### Sort

Basic idea for this is to sorting the array first while maintaining the indexes along with the numbers, so we are to use pair to simplify this in C++, after which everything else is just so intuitive here. The whole solution in C++ is as follows.

```
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t)
{
vector<pair<long, int>> withIndex;
for(int i = 0; i < nums.size(); ++i) withIndex.emplace_back(nums[i], i);
sort(withIndex.begin(), withIndex.end(), [](const pair<long, int>& a, const pair<long, int>&b) { return a.first<b.first; });
for(int i = 0; i < nums.size(); ++i)
{
int j = i+1;
while(j < nums.size())
{
if(withIndex[j].first-withIndex[i].first > t) break;
if(abs(withIndex[j].second-withIndex[i].second) <= k) return true;
j++;
}
}
return false;
}
```

#### Set

Since there is a range we have to keep to search for the valid numbers, so directly we can use `sliding window`

to maintain that feature. As for searching in that window, we should avoid the array or list which will require us to search one by one, which is linear time cost. So as a result we can take advantage of built-in set which can retrieve the range for us in logn instead of n.

```
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t)
{
if(k <= 0) return false;
if(t < 0) return false;
int size = nums.size();
set<int> k_set;
for(int i = 0; i < size; ++i)
{
if(i > k) k_set.erase(nums[i-k-1]);
auto iter = k_set.lower_bound(nums[i]-t);
if(iter!=k_set.end() && *iter<=(long)nums[i]+t) return true;
k_set.insert(nums[i]);
}
return false;
}
```

Notes:

- the first two statements are just used for avoiding futile searching which is actually unnecessary;
- when replacing the
`k_set.lower_bound`

with`lower_bound(k_set.begin(), k_set.end())`

the solution just got TLE; lower_bound though has the feature to locate but it's using linear time cost actually on set instead of logn.