Contains Duplicate III Java

本文主要是介绍Contains Duplicate III Java，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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.

题意及分析：

给出一个数组，要求判断是否存在，对于其中两个不同的元素有：(1) |i-j| <= k (2) |nums[i]-nums[j]| <= t。

TreeSet(binary search tree) o(Nlogk)

利用treeset，用floor方法查找treeSet中大于等于当前值且与当前元素距离小于t的最大元素，然后如果该元素不为空，那么就可以找到符合题意的两个元素。

或者用用ceiling方法查找treeSet中大于等于当前值且与当前元素距离小于t的最小元素，然后如果该元素不为空，那么就可以找到符合题意的两个元素。

最后需要注意的一点，就是两个元素之间的距离要小于等于k，即|i-j|<=k,所以当前treeSet中最多只能有k个元素

class Solution {public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {if(nums==null||nums.length==0||k<=0) return false;TreeSet<Long> treeSet = new TreeSet<Long>();for(int i=0;i<nums.length;i++){final Long floor = treeSet.floor((long)nums[i]+t);final Long ceil = treeSet.ceiling((long)nums[i]-t);if((floor!=null&&floor>=(long)nums[i])||(ceil!=null&&ceil<=(long)nums[i])){return true;}treeSet.add((long)nums[i]);if(i>=k){        //因为元素的坐标差不能超过k，所以在treeSet中最多只能有k个元素treeSet.remove((long)nums[i-k]);}}return false;}
}

这篇关于Contains Duplicate III Java的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---