[LeetCode-JAVA] Contains Duplicate III

浏览数：80 / 时间：2015年06月08日

题目：Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.

思路：相比于I和II，稍微复杂，常规的思路，维护一个长为k的窗口，如果用循环判断会超时，考虑到问题的特性，用TreeSet中的相关方法来实现：

ceiling(e) : 返回set中大于或等于参数e的最小值，无则返回null;

floor(e) : 返回set中小于或等于参数e的最小值，无则返回null;

在k大小的范围内进行判断，每超过一个，从开头出remove一个值。

代码：

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> set = new TreeSet<Long>();
        
        for(int i = 0 ; i < nums.length ; i++){
            if(i-k-1>=0) 
                set.remove((long)nums[i-k-1]);
            if(set.ceiling((long)nums[i]) != null){//大于等于nums[i]的最小元素
                long temp = set.ceiling((long)nums[i]);
                if(Math.abs(temp - nums[i]) <= t)
                    return true;
            }
            if(set.floor((long)nums[i]) != null){//大于等于nums[i]的最小元素
                long temp = set.floor((long)nums[i]);
                if(Math.abs(temp - nums[i]) <= t)
                    return true;
            }
            
            set.add((long)nums[i]);
        }
        return false;  
    }
}

又在网上看到更简洁的方法，也是利用TreeSet中的方法：

SortedSet<E> subSet(E fromElement, E toElement)

返回此 set 的部分视图，其元素从 fromElement（包括）到 toElement（不包括）。

可以直接将两个判断化简在一起（不过LeetCode上没有过 cannot find symbol: class SortedSet 因此需要自己导入包，注意上面的import）。

代码：

import java.util.SortedSet;
public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if(t<0) 
            return false;
        TreeSet<Long> set = new TreeSet<Long>();
        
        for(int i = 0 ; i < nums.length ; i++){
            if(i-k-1>=0) 
                set.remove((long)nums[i-k-1]);
                
            SortedSet<Long> subSet =  set.subSet((long)nums[i]-t, (long)nums[i]+t+1); 
            //t为负的话 fromKey > toKey 因此开始要判断
            if(!subSet.isEmpty()) return true; 
            
            set.add((long)nums[i]);
        }
        return false;  
    }
}