前言

本文中运用了平衡二叉搜索树，也是java里面的TreeSet数据结构。

也运用了桶。感兴趣的朋友可以了解一下。

题目

链接

分析

概述

这篇文章是为中级读者准备的，文章中会介绍了以下几种方法：
二叉搜索树，散列表和桶。

方法一 （线性搜索） 【超时】

思路

将每个元素与它之前的 k个元素比较，查看它们的数值之差是不是在 t以内。

算法

解决这个问题需要找到一组满足以下条件的 i和 j：

我们需要维护了一个k大小的滑动窗口。这种情况下，第一个条件始终是满足的，只需要通过线性搜索来检查第二个条件是否满足就可以了。

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    for (int i = 0; i < nums.length; ++i) {
        for (int j = Math.max(i - k, 0); j < i; ++j) {
            if (Math.abs(nums[i] - nums[j]) <= t) return true;
        }
    }
    return false;
}
// Time limit exceeded.

复杂度分析

• 时间复杂度：O*(*n min(k,n))
  每次搜索都将花费O(min(k,n)) 的时间，需要注意的是一次搜索中我们最多比较 n次，哪怕 k 比 n大。
• 空间复杂度：O(1)
  额外开辟的空间为常数个

方法二 （二叉搜索树） 【通过】

思路

• 如果窗口中维护的元素是有序的，只需要用二分搜索检查条件二是否是满足的就可以了。
• 利用自平衡二叉搜索树，可以在对数时间内通过 插入 和 删除 来对滑动窗口内元素排序。

算法

方法一真正的瓶颈在于检查第二个条件是否满足需要扫描滑动窗口中所有的元素。因此我们需要考虑的是有没有比全扫描更好的方法。

如果窗口内的元素是有序的，那么用两次二分搜索就可以找到 x+t 和 x-t 这两个边界值了。

然而不幸的是，窗口中的元素是无序的。这里有一个初学者非常容易犯的错误，那就是将滑动窗口维护成一个有序的数组。虽然在有序数组中 搜索 只需要花费对数时间，但是为了让数组保持有序，我们不得不做插入和删除的操作，而这些操作是非常不高效的。想象一下，如果你有一个kk大小的有序数组，当你插入一个新元素xx的时候。虽然可以在O(\log k)时间内找到这个元素应该插入的位置，但最后还是需要O(k)的时间来将x插入这个有序数组。因为必须得把当前元素应该插入的位置之后的所有元素往后移一位。当你要删除一个元素的时候也是同样的道理。在删除了下标为ii的元素之后，还需要把下标ii之后的所有元素往前移一位。因此，这种做法并不会比方法一更好。

为了能让算法的效率得到真正的提升，我们需要引入一个支持 插入，搜索，删除 操作的 动态 数据结构，那就是自平衡二叉搜索树。自平衡 这个词的意思是，这个树在随机进行插入,删除操作之后，它会自动保证树的高度最小。为什么一棵树需要自平衡呢？这是因为在二叉搜索树上的大部分操作需要花费的时间跟这颗树的高度直接相关。可以看一下下面这棵严重左偏的非平衡二叉搜索树。

            6
           /
          5
         /
        4
       /
      3
     /
    2
   /
  1

图 1. 一个严重左偏的非平衡二叉搜索树。

在上面这棵二叉搜索树上查找一个元素需要花费 线性 时间复杂度，这跟在链表中搜索的速度是一样的。现在我们来比较一下下面这棵平衡二叉搜索树。

          4
        /   \
       2     6
      / \   /
     1   3  5

假设这棵树上节点总数为 nn，一个平衡树能把高度维持在 h*=logn。因此这棵树上支持在 O*(h)=O(logn) 时间内完成 插入，搜索，删除 操作。

下面给出整个算法的伪代码：

• 初始化一颗空的二叉搜索树 set
• 对于每个元素x，遍历整个数组
  • 在 set 上查找大于等于x的最小的数，如果s−x≤t则返回 true
  • 在 set 上查找小于等于x的最大的数，如果x−g≤t则返回 true
  • 在 set 中插入x
  • 如果树的大小超过了k 则移除最早加入树的那个数。
• 返回 false

我们把大于等于 x 的最小的数 s 当做 x 在 BST 中的后继节点。同样的，我们能把小于等于 x 最大的数 g 当做 x 在 BST 中的前继节点。s 和 g 这两个数是距离 x 最近的数。因此只需要检查它们和 x 的距离就能知道条件二是否满足了。

public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    TreeSet<Integer> set = new TreeSet<>();
    for (int i = 0; i < nums.length; ++i) {
        // Find the successor of current element
        Integer s = set.ceiling(nums[i]);
        if (s != null && s <= nums[i] + t) return true;

        // Find the predecessor of current element
        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;
}

复杂度分析

• 时间复杂度：O*(nlog(min(n,k)))
  我们需要遍历这个 n长度的数组。对于每次遍历，在 BST 中 搜索，插入 或者 删除 都需要花费 O*(logmin(k,n)) 的时间。
• 空间复杂度：O*(min(n,k))
  空间复杂度由 BST 的大小决定，其大小的上限由 k 和 n 共同决定。

笔记

• 当数组中的元素非常大的时候，进行数学运算可能造成溢出。所以可以考虑使用支持大数的数据类型，例如 long。
• C++ 中的 std::set，std::set::upper_bound 和 std::set::lower_bound 分别等价于 Java 中的 TreeSet，TreeSet::ceiling 和 TreeSet::floor。Python 标准库不提供自平衡 BST。
• ceiling(key) 函数：返回大于等于 key 的最小元素，如果不存在，返回空。
• floor() 方法可对一个数进行下舍入，返回给定参数最大的整数，该整数小于或等给定的参数。

方法三 （桶） 【通过】

思路

受 桶排序 的启发，我们可以把 桶 当做窗口来实现一个线性复杂度的解法。

算法

桶排序是一种把元素分散到不同桶中的排序算法。接着把每个桶再独立地用不同的排序算法进行排序。桶排序的概览如下所示：

在上面的例子中，我们有 8 个未排序的整数。我们首先来创建五个桶，这五个桶分别包含[[0,9],[10,19],[20,29],[30,39],[40,49] 这几个区间。这 8 个元素中的任何一个元素都在一个桶里面。对于值为 xx 的元素来说，它所属桶的标签为 x/w，在这里我们让 w = 10。对于每个桶我们单独用其他排序算法进行排序，最后按照桶的顺序收集所有的元素就可以得到一个有序的数组了。

回到这个问题，我们尝试去解决的最大的问题在于：

1. 对于给定的元素 xx, 在窗口中是否有存在区间 [x-t, x+t][x−t,x+t] 内的元素？
2. 我们能在常量时间内完成以上判断嘛？

我们不妨把把每个元素当做一个人的生日来考虑一下吧。假设你是班上新来的一位学生，你的生日在 三月 的某一天，你想知道班上是否有人生日跟你生日在 t=30 天以内。在这里我们先假设每个月都是30天，很明显，我们只需要检查所有生日在 二月，三月，四月 的同学就可以了。

之所以能这么做的原因在于，我们知道每个人的生日都属于一个桶，我们把这个桶称作月份！每个桶所包含的区间范围都是 t，这能极大的简化我们的问题。很显然，任何不在同一个桶或相邻桶的两个元素之间的距离一定是大于 t 的。

我们把上面提到的桶的思想应用到这个问题里面来，我们设计一些桶，让他们分别包含区间 …, [0,t], [t+1, 2t+1], …。我们把桶来当做窗口，于是每次我们只需要检查 x 所属的那个桶和相邻桶中的元素就可以了。终于，我们可以在常量时间解决在窗口中搜索的问题了。

还有一件值得注意的事，这个问题和桶排序的不同之处在于每次我们的桶里只需要包含最多一个元素就可以了，因为如果任意一个桶中包含了两个元素，那么这也就是意味着这两个元素是 足够接近的 了，这时候我们就直接得到答案了。因此，我们只需使用一个标签为桶序号的散列表就可以了。

public class Solution {
    // Get the ID of the bucket from element value x and bucket width w
    // In Java, `-3 / 5 = 0` and but we need `-3 / 5 = -1`.
    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);
            // check if bucket m is empty, each bucket may contain at most one element
            if (d.containsKey(m))
                return true;
            // check the nei***or buckets for almost duplicate
            if (d.containsKey(m - 1) && Math.abs(nums[i] - d.get(m - 1)) < w)
                return true;
            if (d.containsKey(m + 1) && Math.abs(nums[i] - d.get(m + 1)) < w)
                return true;
            // now bucket m is empty and no almost duplicate in nei***or buckets
            d.put(m, (long)nums[i]);
            if (i >= k) d.remove(getID(nums[i - k], w));
        }
        return false;
    }
}

复杂度分析

• 时间复杂度：O(n)

对于这 n 个元素中的任意一个元素来说，我们最多只需要在散列表中做三次 搜索，一次 插入 和一次 删除。这些操作是常量时间复杂度的。因此，整个算法的时间复杂度为 O(n)。

• 空间复杂度：O*(min(n,k))