bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
set<int> window; // set is ordered automatically
for (int i = 0; i < nums.size(); i++) {
if (i > k) window.erase(nums[ik1]); // keep the set contains nums i j at most k
// x  nums[i] <= t ==> t <= x  nums[i] <= t;
auto pos = window.lower_bound(nums[i]  t); // xnums[i] >= t ==> x >= nums[i]t
// x  nums[i] <= t ==> x  nums[i] <= t
if (pos != window.end() && *pos  nums[i] <= t) return true;
window.insert(nums[i]);
}
return false;
}
C++ using set (less 10 lines), with simple explanation.


My solution is similar but I feel it's easier to understand. Basically I check the biggest element smaller than target and smallest element bigger than target in the window to see if any one of them is in the range.
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { set<long long> s; if(k==0) return false; for(int i=0; i<nums.size(); i++){ long long val = nums[i]; if(!s.empty()){ if(s.size()==k+1) s.erase(nums[ik1]); auto higher = s.lower_bound(val); //higher points to smallest element bigger or equal to val if(higher!=s.end()&&(*higherval<=t)) return true; if(higher!=s.begin()) { higher; //now higher should point to biggest element smaller than val auto low = higher; if(low!=s.end()&&((val*low)<=t)) return true; } } s.insert(val); } return false; }
I feel both mine and the one posted by OP doesn't handle cases where there are duplicate values in the window.
10 months later
Now I think OP's solution is the best and duplication is just fine. :)

c++, O(n(logk)), use stl set, for each nums[i], we try to find prev smaller and next larger element of nums[i] from elements nums[i  k, i  1]
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { if(nums.size() <= 1  k <= 0  t < 0){ return false; } multiset<long long> s; for(int i = 0; i < nums.size(); ++i){ if(i  k  1 >= 0){ s.erase(nums[i  k  1]); } s.insert(nums[i]); auto it = s.find(nums[i]); if(it != s.begin()){ it; if(abs(*it  nums[i]) <= t){ return true; } ++it; } if(it != s.end()){ ++it; if(it != s.end() && abs(*it  nums[i]) <= t){ return true; } } } return false; }