leetcode-220

220. 存在重复元素 III

给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

示例：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true

输入：nums = [1,0,1,1], k = 1, t = 2
输出：true

输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false

解法

解法一：暴力解法

超时

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:
        len_nums = len(nums)
        if len(nums) == 1:
            return False
        for i in range(len_nums):
            j = i + k
            
            j = len_nums if j >= len_nums else j+1

                    
            for c in range(i+1,j):
                if abs(nums[i]-nums[c]) <= t:
                            
                    return True

        return False

官方题解一：滑动窗口 + 有序集合

对于序列中每一个元素$x$左侧的最多$k$个元素，如果这$k$个元素中存在一个元素落在区间$[x-t,x+t]$中，我们就找到了一对符合条件的元素。

注意到对于两个相邻的元素，它们各自的左侧的$k$个元素中有$k-1$个重合的。于是我们可以使用滑动窗口的思路，维护一个大小为$k$的滑动窗口，每次遍历到元素$x$时，滑动窗口中包含元素$x$前面的最多$k$个元素，我们检查窗口中是否存在元素落在区间$[x-t,x+t]$即可。

如果使用队列维护滑动窗口内的元素，由于元素是无序的，我们只能对于每个元素都遍历一次队列来检查是否有元素符合条件。如果数组的长度为$n$，则使用队列的时间复杂度为$O(nk)$，会超出时间限制。

因此我们希望能够找到一个数据结构维护滑动窗口内的元素，该数据结构需要满足以下操作：

• 支持添加和删除指定元素的操作，否则我们无法维护滑动窗口；
• 内部元素有序，支持二分查找的操作，这样我们可以快速判断滑动窗口中是否存在元素满足条件，具体而言，对于元素$x$，当我们希望判断滑动窗口中是否存在某个数 $y$ 落在区间$[x-t,x+t]$，只需要判断滑动窗口中所有大于等于 $x-t$ 的元素中是否小于等于 $x+t$即可。

我们可以使用有序集合来支持这些操作。

实现方面，我们在有序集合中查找大于等于$x-t$的最小元素$y$，如果$y$存在，且$y\leq x+t$，我们就找到了一对符合条件的元素。

完成检查后，我们将 $x$ 插入到有序集合中，如果有序集合中元素数量超过了 $k$，我们将有序集合中最早被插入的元素删除即可。

ceiling(E e) 方法返回在这个集合中大于或者等于给定元素的最小元素，如果不存在这样的元素,返回null.

floor(E e)方法返回在这个集合中小于或者等于给定元素的最大元素，如果不存在这样的元素,返回null.

public static boolean containsNearByAlmostDuplicate(int[] nums,int k, int t) {
    int n = nums.length;
    TreeSet<Long> set = new TreeSet<Long>();

    for(int i=0;i<n;i++){

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

        if(ceiling != null && ceiling <= (long)nums[i]+(long)t)
            return true;
        
        set.add((long) nums[i]);

        if(i>=k){
            // System.out.println(nums[i-k]);
            set.remove((long)nums[i-k]); // the slide window forward
        }
        
    }
    return false;
}

官方题解二：桶排序

也可以使用利用桶排序的思想解决本题。我们按照元素的大小进行分桶，维护一个滑动窗口内的元素对应的元素。

对于元素$x$，其影响的区间为 $[ x - t , x + t ]$。故可以设定桶的大小为 $t+1$。

如果两个元素同属一个桶，那么这两个元素必然符合条件。如果两个元素属于相邻桶，那么我们需要校验这两个元素是否差值不超过 $t$。

如果两个元素既不属于同一个桶，也不属于相邻桶，那么这两个元素必然不符合条件。

如果两个不属于相邻桶，说明他们之间的差距已经大于t了

具体地，我们遍历该序列，假设当前遍历到元素 $x$，那么我们首先检查 $x$ 所属于的桶是否已经存在元素，如果存在，那么我们就找到了一对符合条件的元素，否则我们继续检查两个相邻的桶内是否存在符合条件的元素。

实现方面，我们将 $int$ 范围内的每一个整数 $x$ 表示 $x = ( t + 1 ) \times a + b ( 0 \leq b \leq t )$ 的形式，这样$x$ 既归属于编号为$a$的桶。因为一个桶内至多只会有一个元素，所以我们使用哈希表实现即可。

$abs(i-j)\leq k$

$abs(num[i] -num[j])\leq t$

   public static boolean containsNearbyAlmostDuplicate2(int[] nums,int k,int t) {
       int n = nums.length;
       Map<Long,Long> map = new HashMap<Long,Long>();
       long w= (long) t+1; // bucket length

       for (int i = 0; i < n; i++) {
           long id = getID(nums[i], w);
           System.out.println("id "+id);
           
           // in same bucket
           if(map.containsKey(id))
               return true;
           
           // neightbour bucket 
           if( map.containsKey(id-1) && Math.abs(nums[i] - map.get(id-1)) < w ){
               return true;
           }
               
           // neightbour bucket
           if( map.containsKey(id+1) && Math.abs(nums[i] - map.get(id+1)) < w ){
               return true;
           }

           map.put(id, (long) nums[i]);

           if(i >= k){
               map.remove(getID(nums[i-k], w));
           }
       }
       return false;
   }
// 桶编号
   public static long getID(long x,long w) {
       if(x>0)
           return x/w;
       
       return (x+1)/w-1;
   }