LeetCode 220 Contains Duplicate III - 简书

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.

注意题目中一旦出现，当两者距离at most k等constraint时，都可以考虑使用sliding window的方法，每次仅保留window size=k的元素，判断完后再移动并更新window。

思路一：naive thinking
考虑排序，但排序时也得带上index，即需要记录排序前各个元素原先的下标。排序后，check数组中是否存在符合at most t & at most k的元素。

思路二：基于sliding window
顺序扫描数组，每次仅保存size=k的滑动窗口，并用TreeSet或bucket存储窗口中现有的元素，加入新元素后判断是否与集合中元素满足difference<=t的条件。注意窗口的更新，如何维护treeset或bucket（加入新元素的同时，删除最早加入的元素）。

这里要注意为什么需要使用treeset与bucket，而不是queue？原因是treeset和bucket具有根据input value快速查找的能力，若新加入的元素为nums[i]，
则treeset可以通过floor与ceiling在O(log k)的时间复杂度下查找最相近的元素。

Long floor = set.floor((long) nums[i]);         Long ceiling = set.ceiling((long) nums[i]);

bucket可以在O(1)时间复杂度下查找，原因是将出入分成了大小为t+1的桶，这里类似于hashmap，可以根据输入大小nums[i]直接反查在哪个桶中。

long remappedNum = (long) nums[i] - Integer.MIN_VALUE;  long bucket = remappedNum / ((long) t + 1);

Read full article from LeetCode 220 Contains Duplicate III - 简书