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: trueExample 2:
Input: nums = [1,0,1,1], k = 1, t = 2 Output: trueExample 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3 Output: false
存在重复元素III。这道题的前两个版本没什么可说的，这里我直接给出版本三的题解。这道题问的是数组中是否存在两个数他们之间的绝对值 <= t同时他们的index <= k。
思路是用treeset。treeset的特点是里面所有元素是unique的而且所有元素是递增的。同时treeset有两个函数，floor()可以找到treeset中比当前数字小的数字中最大的那一个，ceiling()可以找到treeset中比当前数字大的数字中最小的那一个。这样代码就呼之欲出了。
时间O(nlongk) - treeset的底层是红黑树实现的
空间O(k) - 最多只放了K个元素
Java实现
1 class Solution { 2 public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) { 3 // corner case 4 if (nums == null || nums.length < 2 || k == 0) { 5 return false; 6 } 7 8 // normal case 9 TreeSet<Long> set = new TreeSet<>(); 10 int i = 0; 11 while (i < nums.length) { 12 Long floor = set.floor((long) nums[i]); 13 Long ceiling = set.ceiling((long) nums[i]); 14 if ((floor != null && nums[i] - floor <= t) || (ceiling != null && ceiling - nums[i] <= t)) { 15 return true; 16 } 17 set.add((long) nums[i]); 18 i++; 19 if (i > k) { 20 set.remove((long) nums[i - 1 - k]); 21 } 22 } 23 return false; 24 } 25 }
[LeetCode] 220. Contains Duplicate III
原文：https://www.cnblogs.com/cnoodle/p/13413019.html