[LeetCode] Contains Duplicate III

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: TreeSet.
We maintain a TreeSet of size k. Each time when the size is greater than k, we remove old ones. TreeSet supports the following two operations:

floor(E e)

Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.

ceiling(E e)

Returns the least element in this set greater than or equal to the given element, or null if there is no such element.

Time Complexity: O(n log k). 
Each operation takes O(log k) time.

Space Complexity: O(k).

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

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