LeetCode 220. Contains Duplicate III
题目：https://leetcode.com/problems/contains-duplicate-iii/
题目为：在数组中，给定范围的长度k，判断在这个长度内的数是否有绝对差值小于t的两个数。
Example 2:
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true
Example 3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false
基本思路为：构造一个大小为k的窗口，依次滑动，判断是否满足条件。要求复杂度为n * log(k)。即每次向窗口添加一个元素，共n个，每次添加后判断时复杂度应该为log(k)。理想数据结构为二叉搜索树。
c++实现采用set，内部为红黑树实现的平衡二叉树。
class Solution { public: bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) { set<long> window; // ordered for (int i=0;i < nums.size(); ++i){ // n // maintain a window of size k if (i > k) window.erase(nums[i - k - 1]); // log(k) // find the smallest value x that nums[i] - x <= t auto pos = window.lower_bound(static_cast<long>(nums[i]) - static_cast<long>(t)); // log(k) // check whether x - nums[i] <= t if (pos != window.end() && static_cast<long>(*pos) -static_cast<long>(nums[i]) <= static_cast<long>(t)) return true; window.insert(nums[i]); // log(k) } return false; } };
嗯~由于int 可能溢出，使用了long，应该有更好的办法来处理溢出。
原文：https://www.cnblogs.com/vimery/p/11581725.html