2019-01-30 第五天(#220)

#220 Contains Duplicate III

这道题想要高效实现需要二叉排序树(Binary Sort/Search Tree, BST)的数据结构。二叉树的大小随时保持和k值相同，并且在二叉树中搜索此元素。之所以使用BST是因为它的搜索效率比较高。
现在来稍微转化一下这个问题：（j为需要搜索的元素）
差的绝对值小于t =》
|nums.at(i) - j| <= t
num.at(i) + t <= j <= num.at(i) - t
那么目标就变成搜索满足以上条件的j。
在C++中，BST由std::set<template>实现。它和之前的unordered_set类似，唯一的区别就是其中的元素是得到了排序的。
代码如下：

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        set<long> binary_st;
        for(int i = 0; i < nums.size(); i++) {
            if (i > k) binary_st.erase(nums[i-k-1]);
            auto pos = binary_st.lower_bound((long) nums[i] - t); 
            if (pos != binary_st.end() && t >= *pos - nums[i]) return true;
            binary_st.insert(nums[i]);
        }
        
        return false;
    }
        
};