220. Contains Duplicate III

本题我其实也算是坐下来了，但是用的方法在思路上也很接近标准答案，但是还是复杂了一些，写起来更容易出错。

算法：

• 设定一个TreeSet<Long>，来保存最近的K个数字
• 在遍历到一个新的数字的时候，寻找在TreeSet<Long>里面：
  • floor(): 比这个数字小的最大的数
  • ceiling(): 比这个数字大的最小的数
• 如果上面两个数存在，则意味着这两个数必然满足index差在K之内这个条件

• 只需要看看这两个数是不是有一个跟遍历的数字差别在t以内

  • 我以前想错了的是：遍历TreeSet<Long>里面的所有元素，其实大可不必，只需要这两个

• 时间复杂度：

• 空间复杂度:

代码如下：

class Solution {
  public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    if (t < 0) {
      return false;
    }
    TreeSet<Long> set = new TreeSet<>();
    for (int i = 0; i < nums.length; ++i) {
      Long num = new Long(nums[i]);
      if (set.ceiling(num) != null && set.ceiling(num) - num <= t) {
        return true;
      }
      if (set.floor(num) != null && num - set.floor(num) <= t) {
        return true;
      }
      set.add(num);
      if (i >= k) {
        set.remove(new Long(nums[i-k]));
      }
    }
    return false;
  }
}