Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

Solution:

  1. public class Solution {
  2.   public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
  3.     TreeSet<Integer> tree = new TreeSet<>();
  5.     for (int i = 0; i < nums.length; i++) {
  6.       Integer ceil = tree.ceiling(nums[i] - t);
  7.       Integer floor = tree.floor(nums[i] + t);
  9.       if ((ceil != null && ceil <= nums[i]) || (floor != null && floor >= nums[i])) {
  10.         return true;
  11.       }
  13.       tree.add(nums[i]);
  15.       if (i >= k) {
  16.         tree.remove(nums[i - k]);
  17.       }
  18.     }
  20.     return false;
  21.   }
  22. }