# Short C++ solution

• ``````class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
map<long long,int> M;
int l=0;
for (int r=0;r<nums.size();r++) {
if (r-l>k && M[nums[l]]==l)
M.erase(nums[l++]);
auto it=M.lower_bound(nums[r]-t);
if (it!=M.end() && abs(it->first-nums[r])<=t)
return true;
M[nums[r]]=r;
}
return false;
}
};``````

• ``````if (r-l>k && M[nums[l]]==l)
``````

the second judgement statement seems needless, cos every time u assign the map with M[nums[r]]=r;
anyway it's an excellent solution though~~

• is that a problem that the second judgement still there but without a check in if (it!=M.end() && abs(it->first-nums[r])<=t) about the interval? will it return a wrong answer since the interval already excess k?

• Hi! This is my solution. Share the same idea with you.

``````class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
map<int, int> m;
for(int i = 0; i < nums.size(); ++i) {
auto it = m.lower_bound(nums[i] - t);
while(it != m.end() && it->second < i - k)  it = m.erase(it);
if(it != m.end() && nums[i] >= it->first - t)
return true;
m[nums[i]] = i;
}
return false;
}
};``````

• @fastcode I change you solution,It can not pass the case
[-2147483648,-2147483647]
3
3
code here:

``````class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
map<long long, int> map;
for (int i = 0; i < nums.size(); ++i)
{
auto it = map.lower_bound((long long)nums[i] - (long long)t);
while (it != map.end() && i - it->second > k)
it = map.erase(it);
if (it != map.end() && abs(nums[i] - it->first) <= t)
return true;
map[nums[i]] = i;
}
return false;
}
};
``````

• @fastcode your solution is wrong

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.