LeetCode(108) -- 220

P220. Contains Duplicate III (Medium)

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

My Solution

public class P220_ContainsDuplicateIII {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        for (int i = 0; i < nums.length; i++) {
            int length = Math.min(nums.length - i, k + 1);
            int[] copy = new int[length];
            System.arraycopy(nums, i, copy, 0, length);
            Arrays.sort(copy);
            for (int j = 1; j < copy.length; j++) {
                long curr = copy[j];
                long prev = copy[j - 1];
                if (curr - prev <= (long) t) {
                    return true;
                }
            }
        }
        return false;
    }
}

超时了！！

Solution

方法二： Binary Search Tree

用一个TreeSet来保存size最多为k的一个window的所有数。新插入的数，如果它左边或者右边的数跟它的距离小于等于t，则说明找到了正确答案。

注意这里允许的window实际上是k+1,但是每次我们需要在插入之前去比较，所以维护一个size为k的window.

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            Integer s = set.ceiling(nums[i]);
            if (s != null && s <= nums[i] + t) {
                return true;
            }
            Integer g = set.floor(nums[i]);
            if (g != null && nums[i] <= g + t) {
                return true;
            }
            set.add(nums[i]);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}

72%

方法三： Buckets

分成宽度相等的篮子，往每个篮子里放，如果左右两边的篮子有东西，那么就看是不是离得足够近。

class Solution {
    private long getID(long x, long w) {
        return x < 0 ? (x + 1) / w - 1 : x / w;
    }

    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (t < 0) {
            return false;
        }
        Map<Long, Long> d = new HashMap<>();
        long w = (long) t + 1;
        for (int i = 0; i < nums.length; i++) {
            long m = getID(nums[i], w);
            if (d.containsKey(m)) {
                return true;
            }
            if (d.containsKey(m - 1) && nums[i] - d.get(m - 1) < w) {
                return true;
            }
            if (d.containsKey(m + 1) && d.get(m + 1) - nums[i] < w) {
                return true;
            }
            d.put(m, (long) nums[i]);
            if (i >= k) {
                d.remove(getID(nums[i - k], w));
            }
        }
        return false;
    }
}