leetcode--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 difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
題意:整形配列を1つ与えて、2つのシーケンス番号i,jが存在するかどうかを検査して、nums[i]とnums[j]の差が最も多くtであることを要求して、同時にiとjの差が最も多くkである
分類:ツリー
解法1:長さkのウィンドウを維持し、新しい値と元のウィンドウの値の差がtを超えるかどうかをチェックするたびに考えやすい.
二重ループを使用すると,時間複雑度がO(nk)でタイムアウトする.TreeSetを用いて差分値を調べ,複雑度をO(nLogk)とした.

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

setのsubSet()メソッドは、set内のこの範囲内のデータを元のset内で指定し、新しいSortedSetを構成して返すことができます.

import java.util.SortedSet;
public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        //input check  
        if(k<1 || t<0 || nums==null || nums.length<2) return false;  
          
        SortedSet<Long> set = new TreeSet<Long>();  
        for(int j=0; j<nums.length; j++) {  
        	SortedSet<Long> subSet =  set.subSet((long)nums[j]-t, (long)nums[j]+t+1); //        ，     t      ，         SET
            if(!subSet.isEmpty()) return true;//       ，        
              
            if(j>=k) {//        ，  SET         
                set.remove((long)nums[j-k]);  
            }  
            set.add((long)nums[j]);//        
        }  
        return false;  
    }
}

同じ考えで、私たちはこのように書くことができます.

public class Solution {
    public boolean containsNearbyAlmostDuplicate(final int[] nums, int kk, long t) {
        if (nums.length < 2) return false;
        if (kk == 0) return false;
        TreeSet<Long> window = new TreeSet<Long>();

        for(int i=0;i<nums.length;i++) {
            // check dup, window size <= kk right now
            if ( window.floor(nums[i] + t) !=null && window.floor(nums[i]+t) >= nums[i]-t ) return true;
            window.add(new Long(nums[i]));
            if (i >= kk) {
                //remove one, the size has to be kk on the next fresh step
                window.remove(new Long(nums[i-kk]));
            }
        }
        return false;
    }
}