# 220 LeetCode Java: Contains Duplicate III – Medium

### Problem:

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] andnums[j] is at most t and the difference between i and j is at most k.

### Thoughts:

This is a very difficult one if you don’t know there is a class called TreeSet.

With the help of TreeSet, it just becomes super easy.

A TreeSet is keeping all elements in k range based on current index.

Alternative solution is to use a HashMap to keep the index for an element.

### Solutions:

``````public class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (k < 1 || t < 0)
return false;
SortedSet<Long> set = new TreeSet<Long>();
for (int i = 0; i < nums.length; i++) {
long left = (long) nums[i] - t;
long right = (long) nums[i] + t + 1;
SortedSet<Long> subSet = set.subSet(left, right);
if (!subSet.isEmpty())
return true;
if (i >= k) {
set.remove((long) nums[i - k]);
}
}
return false;
}
}
``````

Alternative:

···java public class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { HashMap> index = new HashMap>(); for (int i = 0; i < nums.length; i ++) { if (!index.containsKey(nums[i])) { index.put(nums[i], new LinkedList()); } index.get(nums[i]).add(i); } Arrays.sort(nums); for (int i = 0; i < nums.length - 1; i ++) { for (int j = i + 1; j < nums.length; j ++) { int diff = nums[j] - nums[i]; if (diff >= 0 && diff <=t) { for (Integer a:index.get(nums[j])) { for (Integer b:index.get(nums[i])) { if (a!=b && Math.abs(a-b) <= k ) { return true; } } } } else { break; } } } return false; } } ```