Question
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
Algorithm
Use 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 tonums[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.
Code
Java
-
import java.util.SortedSet; import java.util.TreeSet; public class Contains_Duplicate_III { class Solution { public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { if (nums == null || nums.length < 2 || k < 0 || t < 0) { return false; } TreeSet<Long> set = new TreeSet<>(); // long because int will possibly be overflow for (int i = 0; i < nums.length; i++) { long current = (long) nums[i]; long leftBoundary = (long) current - t; long rightBoundary = (long) current + t + 1; // right boundary is exclusive, so +1 SortedSet<Long> sub = set.subSet(leftBoundary, rightBoundary); if (sub.size() > 0) { return true; } set.add(current); // to keep the index diff <=k if (i >= k) { // or if(set.size()>=k+1) set.remove((long) nums[i - k]); } } return false; } } }
-
// OJ: https://leetcode.com/problems/contains-duplicate-iii/ // Time: O(NlogK) // Space: O(K) class Solution { public: bool containsNearbyAlmostDuplicate(vector<int>& A, int k, int t) { if (t < 0) return false; multiset<long> s; for (int i = 0; i < A.size(); ++i) { if (i > k) s.erase(s.find(A[i - k - 1])); if (s.lower_bound((long)A[i] - t) != s.upper_bound((long)A[i] + t)) return true; s.insert(A[i]); } return false; } };
-
''' bisect: maintaining a list in sorted order without having to sort the list after each insertion. https://docs.python.org/3/library/bisect.html bisect.bisect_left() Locate the insertion point for x in a to maintain sorted order. bisect.bisect_right() or bisect.bisect() Similar to bisect_left(), but returns an insertion point which comes after (to the right of) any existing entries of x in a. ''' import bisect class Solution(object): def containsNearbyAlmostDuplicate(self, nums, k, t): """ :type nums: List[int] :type k: int :type t: int :rtype: bool """ if k == 0: return False bst = [] if k < 0 or t < 0: return False for i, num in enumerate(nums): idx = bisect.bisect_left(bst, num) if idx < len(bst) and abs(bst[idx] - num) <= t: return True if idx > 0 and abs(bst[idx - 1] - num) <= t: return True if len(bst) >= k: del bst[bisect.bisect_left(bst, nums[i - k])] bisect.insort(bst, num) return False