Leetcode - Contains Duplicate II

My code:

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (k < 1 || t < 0) {
            return false;
        }
        Map<Long, Long> map = new HashMap<Long, Long>();
        for (int i = 0; i < nums.length; i++) {
            long curr = (long) nums[i];
            long bucket = (curr - Integer.MIN_VALUE) / ((long) t + 1);
            if (map.containsKey(bucket)) {
                return true;
            }
            else if (map.containsKey(bucket - 1) && curr - map.get(bucket - 1) <= t) {
                return true;
            }
            else if (map.containsKey(bucket + 1) && map.get(bucket + 1) - curr <= t) {
                return true;
            }
            map.put(bucket, curr);
            if (i >= k) {
                map.remove(((long) nums[i - k] - Integer.MIN_VALUE) / ((long) t + 1));
            }
        }
        
        return false;
    }
}

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

最快的方法，是用 bucket sort
time complexity: O(n)
注意细节是，都是 强制转换成long 型，包括 t !
其次， nums[i] - Integer.MIN_VALUE 拿到偏移量，算出 bucket
这个想法很重要。

还有种做法是用TreeSet
My code:

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (k < 1 || t < 0) {
            return false;
        }
        TreeSet<Long> set = new TreeSet<Long>();
        for (int i = 0; i < nums.length; i++) {
            long curr = (long) nums[i];
            long left = curr - t;
            long right = curr + t + 1;
            SortedSet<Long> sub = set.subSet(left, right);
            if (sub.size() > 0) {
                return true;
            }
            set.add((long) nums[i]);
            if (i >= k) {
                set.remove((long) nums[i - k]);
            }
        }
        
        return false;
    }
}

reference:
http://www.programcreek.com/2014/06/leetcode-contains-duplicate-iii-java/

这个思路比较常规。

总体的总结：
https://leetcode.com/articles/contains-duplicate-iii/#approach-3-buckets-accepted

Anyway, Good luck, Richardo! -- 10/14/2016