Formatted question description: https://leetcode.ca/all/220.html
220. 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 absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k. Example 1: Input: nums = [1,2,3,1], k = 3, t = 0 Output: true Example 2: Input: nums = [1,0,1,1], k = 1, t = 2 Output: true Example 3: Input: nums = [1,5,9,1,5,9], k = 2, t = 3 Output: false @tag-array
TreeSet to solve, used to record the mapping between numbers and index.
most important difference between HashSet and TreeSet is ordering:
HashSet doesn’t guaranteed any order, while TreeSet maintains objects in Sorted order defined by either Comparable or Comparator method
Two pointers i and j are needed here. At first, both i and j point to 0, and then i starts to traverse the array to the right.
- If the difference between i and j is greater than k, and there is nums[j] in the map, delete it from the TreeSet and j move 1 step to the right. This ensures that the difference between the index of all the numbers in TreeSet is not greater than k,
- Then we use TreeSet
subSet()function to find numbers greater than or equal to
nums[i]-t, and the absolute value of the difference between all numbers less than this threshold and nums[i] will be greater than t.
- Then check all the following numbers, and return true if the absolute value of the difference between the numbers is less than or equal to t. Finally traverse the entire array and return false
The treeSet is essentially a balanced binary search tree.
- We put k elements in the treeSet, which is a sliding window.
- So when we insert an element to the treeSet, we need to remove one from the end.
So the basic idea is for each element nums[i], we check if there is any element between
[nums[i] - t, nums[i] + t].
If yes, return true.