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 absolutedifference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

二刷
Version #2 Bucket
Time O(n)
Space O(n / t)
65.99 %
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (t < 0) {
            return false;
        }
        // window [index - k, index]
        // Put all elements into buckets
        // position = nums[index] / (t + 1)
        // e.g. t=2  position   0      1      2
        //           bucket   0,1,2  3,4,5  6,7,8
        // If element is negative, we'll have negative index -> we need to normalize -> subtract minimum num from all elements
        int min = Integer.MAX_VALUE;
        for (int num : nums) {
            min = Math.min(min, num);
        }
        long lt = Long.valueOf(t);
        Map<Long, Long> map = new HashMap<>();
        for (int index = 0; index < nums.length; index++) {
            long curr = Long.valueOf(nums[index]) - min;
            long position = curr / (lt + 1);
            if (map.containsKey(position)
               || (map.containsKey(position - 1) && curr - map.get(position - 1) <= t)
               || (map.containsKey(position + 1) && map.get(position + 1) - curr <= t)) {
                return true;
            }
            map.put(position, curr);
            if (index >= k) {
                map.remove((Long.valueOf(nums[index - k]) - min) / (lt + 1));
            }
        }
        return false;   
    }
}

Version #1 TreeSet
Time O(nlogk) Space O(k)
一直纠结用TreeSet的话，是怎么处理duplicate的问题
譬如 [6, 0, 6, 8, 17]  k = 2, t = 1 -> 当window [0, 6, 8] 的时候remove 第一个6， 就会把第二个6 也从set里面remove出去
后来想了一下，我是不是傻子？ 如果window 有duplicate, 那么 6 - 6 = 0 符合一切 diff < t， 在之前一步就已经return true了

20.87 %
class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        // window [index - k, index]
        TreeSet<Integer> set = new TreeSet<>();
        for (int index = 0; index < nums.length; index++) {
            Integer ceil = set.ceiling(nums[index]);
            Integer floor = set.floor(nums[index]);
            if ((ceil != null && Long.valueOf(ceil) - Long.valueOf(nums[index]) <= t)
               || (floor != null && Long.valueOf(nums[index]) - Long.valueOf(floor) <= t)) {
                return true;
            }
            set.add(nums[index]);
            if (index >= k) {
                set.remove(nums[index - k]);
            }
        }
        return false;
    }
}

一刷
给一个unsorted array nums[i]
一个sliding window size k
把window里面的element 都放进TreeSet 里面， 用logk的时间找到离nums[i]最近的比nums[i] 大或等于的数/小或等于的数
如果diff小于k，就返回true

concern #1 duplicates
window 是在index i 以前， 因为num[i]还没有加入到TreeSet里面 所以不会被吃掉
即使TreeSet里面有和nums[i] 一样的数也是可以找到的

concern #2 window size = k
向后找index = i，那它和window最左边的元素的坐标差是？
e.g.
k = 3
 index  0   [1    2    3]   4    5    6
index 4 和index 1之差是3 ， 3 == k


写了一个bug

Input:[-1,-1] 1 0

Output:false

Expected:true

问题是写了k <= 1就返回false
其实 k 是可以等于1的，这样是两数相邻的情况



还有一个溢出的问题

Input:[-1,2147483647] 1 2147483647

Output:true

Expected:false

Version #1
TreeSet
ceiling(E e)

Returns the least element in this set greater than or equal to the given element, or null if there is no such element.

floor(E e)

Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.

22.27 %
Time O(nlogk)
Space O(k)

public class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        // k is window size
        // t is max diff
        if (nums == null || nums.length <= 1 || k < 1) return false;
        // set of numbers
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            // candidate is the closest number smaller than nums[i]
            Long diff = 0L;
            Integer smaller = set.floor(nums[i]);
            if (smaller != null) {
                diff = nums[i] - (long)smaller;
                if (diff <= t) return true;
            }
         
            Integer larger = set.ceiling(nums[i]);
            if (larger != null) {
                diff = (long)larger - nums[i];
                if (diff <= t) return true;
            }
     
            // k = 3
            // index 0 1 2 3
            if (set.size() == k) {
                set.remove(nums[i - k]);
            }
            set.add(nums[i]);
        }
        return false;
    }
}

Version #2
算法哥写了一个lower bound和upper bound的方法
可以少做一次treeset search