My code:
import java.util.TreeSet;
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums == null || nums.length == 0)
return false;
if (k <= 0 || t < 0)
return false;
TreeSet<Integer> s = new TreeSet<Integer>();
for (int i = 0; i < nums.length; i++) {
int c = nums[i];
if ((s.floor(c) != null && (long)c - s.floor(c) <= t)
|| (s.ceiling(c) != null && s.ceiling(c) - (long)c <= t))
return true;
else
s.add(c);
if (i >= k)
s.remove(nums[i - k]);
}
return false;
}
}
My test result:
这个作业有点难度啊，我没想出来解法，就看了答案。
这是我第一次用 binary search tree数据结构，也就是 TreeSet. 他的内部是用红黑树来实现的。那么，借助 BST，我们到底能干吗呢？
利用他的两个方法，ceiling and floor
ceiling 是得到和传入参数最近且大于传入参数的值。
floor 是得到和传入参数最近且小于传入参数的值。
那么，我得到了一个 nums[i], 接着我用BST来查询这棵树中距离nums[i]最近且大于他的数，是否为空，如果为空，那他就是最大。则无操作。如果有，取过来，判断下两者的差值是否小于等于t，如果是那就返回true。
同样，floor是得到和传入参数最近且小于传入参数的值。所以如果为空，那他就是最小。如果有，取过来，判断下，两者的差值是否小于等于t，如果是，就返回true。
当然，上面所说的这些，都有一个前提。即，存入Tree的结点，它们之间的间距不超过k。所以可以只关注t的要求，放心大胆的做。
那么，对于一个特定的结点，他需要考虑的情况就是，
[i - k, i + k] 范围内的所有情况，其他情况即使符合t，也没用。
然后，需要考虑到的一点是，我们不需要考虑 i + 1, i + 2, .....i + k 的情况。因为他们都还没有被插入到Tree中。那么，你一定会问，这些情况不会被遗漏掉吗？
不会的，因为， 当 i = i + k 的时候， i, i + k 这样的情况会再次被考虑。
所以，我们只需要考虑前边的情况，同时，每前进一个结点，就把k范围外的结点给删除处Tree，以保证结果的准确性。
差不多就这样了，思路还是挺妙的，尤其是解决k局限性问题的思路。
附带两个解决问题的博客。
http://www.programcreek.com/2014/06/leetcode-contains-duplicate-iii-java/
http://bookshadow.com/weblog/2015/06/03/leetcode-contains-duplicate-iii/
**
总结： 第一次使用 TreeSet，floor, ceiling, add,remove
希望妹子可以真的努力起来，对自己残忍起来。然后，以后，我想象了太多以后美好的生活，我想活到到时候，而你，也在我身边。
希望明天体检一切顺利，不要检查出 癌症。
**
Anyway, Good luck, Richardo!
public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (nums == null || nums.length < 2 || k < 1 || t < 0)
return false;
TreeSet<Long> helper = new TreeSet<Long>();
for (int i = 0; i < nums.length; i++) {
Long left = (long) nums[i] - t;
Long right = (long) nums[i] + t + 1;
/** return set's value from [left, right) */
Set<Long> subSet = helper.subSet(left, right);
if (!subSet.isEmpty())
return true;
helper.add((long) nums[i]);
if (i >= k)
helper.remove((long) nums[i - k]);
}
return false;
}
}
第二遍做也没能做出来。
看了答案，还是遗漏了，
TreeSet这个数据结构，其实就是binary search tree(内部用红黑树实现)。
然后我就把nums[i] 插入该棵树，然后调用他的系统方法：
tree.subSet(left, right); // 找出值在 [left, right) 区域，放入set中返回
如果返回的set非空，代表存在这样的value。那么下面就需要判断index是否符合条件，这个马上说。
**
TreeSet, 如果不存在符合条件的value，返回的set不一定是null！！但一定是empty!!!
**
那么index是否符合条件呢?在这个treeset中，我只存
index： [i - k + 1, i] 这一段index对应的value。
即每次都把之前区域外的index给删了。
如果满足条件的value在右侧，那么下次访问他时仍然可以找到，不会有任何遗漏。
果然是巧！
吃饭去了，有点紧张！
Anyway, Good luck, Richardo!
