# 220. Contains Duplicate III

Reference: LeetCode

Difficulty: Medium

## Problem

Given an array of integers, find out whether there are two distinct indices

`i`

and`j`

in the array such that the absolute difference between`nums[i]`

and`nums[j]`

isat most`t`

and the absolute difference between`i`

and`j`

isat most`k`

.

**Example:**

1 | Input: nums = [1,2,3,1], k = 3, t = 0 |

## Analysis

### Tree Set

Based on the solution in Contains Duplicate II, we use a tree set to keep `k`

elements in ascending order.

Then we find the closest elements of `nums[i]`

. We do binary search for value `nums[i]`

to find the `floor`

and `ceiling`

elements, and compare them with `nums[i]`

to see if the requirement is satisfied.

**Note:**

- At the beginning, the tree set is empty.
- Use
`Long`

type to solve the overflow problem.

1 | public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { |

**Time:** $O(N\log{(\min(N, k))})$**Space:** $O(\min(N, k))$

Comment