[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.

SOL1:

 public class Solution {

     public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {

         if(nums == null || nums.length == 0 || t < 0)

             return false;

         TreeSet<Long> ts = new TreeSet<>();

         for(int i = 0; i < nums.length; ++i) {

             if(i > k)

                 ts.remove((long)nums[i - k - 1]);

             TreeSet<Long> temp = (TreeSet<Long>) ts.subSet((long)nums[i] - t, true,(long)nums[i] + t, true);

             if(!temp.isEmpty())

                 return true;

             ts.add((long)nums[i]);

         }

         return false;

     }

 }

SOL2:

利用bucket来做：

https://leetcode.com/discuss/38206/ac-o-n-solution-in-java-using-buckets-with-explanation

巴特西

[Leetcode] Contains Duplicate III

最新文章

热门文章