This is my first thought on this problem, sort the input with index info saved and search as far as the value difference is less than or equal to k. For worst case scenario, the search would be O(n^2), but this solution is surprisingly fast, my thought would be the test cases are not covering the case that all the input is within the value difference of k.

```
public class Solution {
class Pair {
int val;
int index;
Pair(int v, int i) {
this.val = v;
this.index = i;
}
}
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums == null || nums.length < 2 || t < 0 || k < 1) {
return false;
}
int len = nums.length;
Pair[] pair = new Pair[len];
for(int i = 0; i < len; i++) {
pair[i] = new Pair(nums[i], i);
}
Arrays.sort(pair, new Comparator<Pair> () {
public int compare(Pair p1, Pair p2) {
return p1.val - p2.val;
}
});
for(int i = 0; i < len; i++) {
for(int j = i + 1; j < len && Math.abs((long)pair[j].val - (long)pair[i].val) <= (long)t; j++){
int indexDiff = Math.abs(pair[i].index - pair[j].index);
if (indexDiff <= k) {
return true;
}
}
}
return false;
}
}
```