LeetCode OJ 220.Contains Duplicate 3

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.

这个问题在前一个问题的基础上又对nums[i],nums[j]的关系作了约束，要求|nums[i]-nums[j]|<=t && |i-j|<=k;

对于这个问题，在前面代码的基础上，一个很自然的做法是：

 1 public class Solution {
 2     public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
 3         Map<Integer,Integer> map = new HashMap<>(0);
 4         
 5         for(int i=0; i<nums.length; i++){
 6             for(int num : map.keySet()){
 7                 if(Math.abs(num-nums[i])<t && i-map.get(num)<k) return true;
 8             }
 9             map.put(nums[i],i);
10             if(map.size()>k) map.remove(nums[i-k]);
11         }
12         return false;
13     }
14 }

这是一个两层的循环，对于每一个nums[i]，把它与Map中包含的其他所有元素进行比较，检查是否有满足条件的元素。这个方法很容易理解，但是时间复杂度太高，如果k很大的话，内层循环的迭代次数会很多。导致Time Limit Exceeded。

如何才能对该算法进行改进呢？在参考了别人的代码后，发现了一个很机智的解法，它的时间复杂度是O(n)，先把代码贴出来如下：

 1 public class Solution {
 2     public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
 3         if (t < 0) return false;
 4     Map<Long, Long> d = new HashMap<>();
 5     long w = (long)t + 1;
 6     for (int i = 0; i < nums.length; ++i) {
 7         long m = getID(nums[i], w);
 8         if (d.containsKey(m))
 9             return true;
10         if (d.containsKey(m - 1) && Math.abs(nums[i] - d.get(m - 1)) < w)
11             return true;
12         if (d.containsKey(m + 1) && Math.abs(nums[i] - d.get(m + 1)) < w)
13             return true;
14         d.put(m, (long)nums[i]);
15         if (i >= k) d.remove(getID(nums[i - k], w));
16     }
17     return false;
18     }
19     
20     private long getID(long i, long w) {
21     return i < 0 ? (i + 1) / w - 1 : i / w;
22 }
23 }

接下来我们对该算法进行分析。首先我们来看下getID函数的功能。

i>=0时，ID是i/w。举个例子，假设t=2，则w=3。如果nums[] = {0,1,2,3,4,5,6,7}。

nums[0]/w = 0/3 = 0;

nums[1]/w = 1/3 = 0;

nums[2]/w = 2/3 = 0;

nums[3]/w = 3/3 = 1;

nums[4]/w = 4/3 = 1;

nums[5]/w = 5/3 = 1;

nums[6]/w = 6/3 = 2;

这样就把nums[i]按照值的不同划分到了不同的组中。如果存在两个数|nums[i]-nums[j]|<=t，那么这两个数的ID或者相同，或者至多相差1。

同样i<0时，ID是(i+1)/w - 1。同样假设w=3，nums[]={-6,-5,-4,-3,-2,-1}。

nums[0]/w = (-6+1)/3 -1 = -3;

nums[1]/w = (-5+1)/3 -1 = -3;

nums[2]/w = (-4+1)/3 -1 = -2;

nums[3]/w = (-3+1)/3 -1 = -2;

nums[4]/w = (-2+1)/3 -1 = -2;

nums[5]/w = (-1+1)/3 -1 = -1;

这样就把nums[i]按照值的不同划分到了不同的组中。如果存在两个数|nums[i]-nums[j]|<=t，那么这两个数的ID或者相同，或者至多相差1。

可以发现，这两个划分是连续的。ID=···-n,···,-1,0,1,···,n···。

那么对于每一个nums[i]，先计算它的ID，然后在Map中判断是否包含此ID，如果包含，那么肯定存在这样的两个数，他们之间的差小于等于t。否则的话判断是否存在与此ID相差为1的ID，即ID-1，ID+1。如果存在的话，判断两个数之间的差是否小于w（即小于等于t）。对于其他的ID，其实是没有必要来判断的。可以看到，提前计算ID的过程使得对于每一个nums[i]，不需要像上一个算法中对Map中的每个数进行比较，而最多只需要进行三次比较即可判断出是否有满足条件的元素。