博文中会简要介绍Leetcode P0220题目分析及解题思路。

“Contains Duplicate III”是p0217的衍生题，这道题相对难一些。根据题目要求，我们首先可以得出这道题也考察了滑动窗口的解题思想，由于要求下标之间的差最多为k，所以滑动窗口的长度固定在k。除此之外，这道题要求得到与某个数的差不超过t的数是否在窗口中存在，所以当我们得到当前窗口内所有数以后，对于每个数，我们都需要找到其在大小关系上的左边的数left和右边的数right，如果left或right中有一个与它的差不超过t则说明我们找到了指定的数，则可以返回true。

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

我们不难注意到，这道题其实要求在滑动窗口内有序，这样我们就可以保证在下标差不超过k的窗口内，以O(log n)的时间复杂度找到比某个数大的最小数upper和比某个数小的最大数lower。

根据上述要求我们可以引入TreeMap来解决这个问题。TreeMap的底层实现是红黑树，即一种特殊的平衡二叉搜索树，也就是说TreeMap中的元素是有序的唯一的，所以使用TreeMap可以很容易地得到任意一个数在这个容器里的上下确界，即lower和upper。

那么对于遍历到的每个数num，我们使用TreeMap结构存储它们，并且维护这个结构的容量始终不超过k，然后对num的上下界进行检索，得到其在容器内的上下确界，最后比较上下确界和num的差是否不超过t即可。

以下是Java的题解代码实现。

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        TreeSet<Long> kNumSet = new TreeSet<>();
        int N = nums.length;
        for (int idx=0; idx<N; ++idx) {
            long num = nums[idx];
            // Find the successor of current element
            Long lower = kNumSet.floor(num);
            if (lower != null && lower >= num-t)
                return true;
            
            // Find the predecessor of current element
            Long upper = kNumSet.ceiling(num);
            if (upper != null && upper <= num+t)
                return true;
            
            kNumSet.add(num);
            if (kNumSet.size() > k) 
                kNumSet.remove((long) nums[idx-k]);
        }
        
        return false;
    }
}

以下是C++的题解代码实现。

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<long> k_num_set;
        int N = nums.size();
        for (int idx=0; idx<N; ++idx) {
            long num = nums[idx];
            
            // c++里set实现了红黑树，便于检索，
            // lower_bound返回一个上确界，upper_bound返回一个上界
            auto upper = k_num_set.lower_bound(num-t);
            if (upper != k_num_set.cend() && abs(*upper-num) <= t) 
                return true;
            
            k_num_set.insert(num);
            if (k_num_set.size() > k)
                k_num_set.erase(nums[idx-k]);
        }
        
        return false;
    }
};