2015年11月3日星期二

Leetcode 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 difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
Solution 1: compare to II, use Tree Map instead of Hashmap could solve it.
 public class Solution {  
   public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {  
     int n=nums.length, i=0;  
     if (t<0) return false;  
     TreeSet<Integer> set=new TreeSet<>();  
     for (int j=0; j<n; j++) {  
       if (j-i>k) set.remove(nums[i++]);  
       int lo=(nums[j]<Integer.MIN_VALUE+t)?Integer.MIN_VALUE:nums[j]-t;  
       int hi=(nums[j]>Integer.MAX_VALUE-t)?Integer.MAX_VALUE:nums[j]+t;  
       if (set.ceiling(lo)!=null && set.ceiling(lo)<=hi) return true;  
       set.add(nums[j]);  
     }  
     return false;  
   }  
 }  

没有评论:

发表评论