[LeetCode 220] Contain Duplicate III

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

Diffculty
Medium

Similar Problems
[LeetCode ] Contains Duplicate Easy [LeetCode ] Contains Duplicate II Easy

Analysis

利用multiset进行BST的二分搜索。lower_bound()返回一个迭代器，指向大于等于输入值的第一个元素。 从左到右扫描数组，若multiset的元素数量等于k+1，则删去最先进入的元素。由于multiset.size()始终小于等于k+1， 所以下标之差是肯定小于等于k的。然后利用lower_bound()，找到第一个大于等于nums[i]-t的元素，若该元素和nums[i]的差的绝对值小于等于t，则返回真。

注意：为了防止溢出，必须将数据转化为long long进行处理！

class Solution { public: bool containsNearbyAlmostDuplicate(vector& nums, int k, int t) { multiset bst; for (int i = 0; i < nums.size(); ++i) { if (bst.size() == k + 1) bst.erase(bst.find(nums[i - k - 1])); auto lb = bst.lower_bound(nums[i]); if (lb != bst.end() && abs(lb - nums[i]) <= t) return true; auto ub = bst.upper_bound(nums[i]); if (ub != bst.begin() && abs((--ub) - nums[i]) <= t) return true; bst.insert(nums[i]); } return false; } };

直接找nums[i] - t的lower_bound, 这个值就是与nums[i]差值最近的值。 class Solution { public: bool containsNearbyAlmostDuplicate(vector& nums, int k, int t) { multiset bst; for (int i = 0; i < nums.size(); ++i) { if (bst.size() == k + 1) bst.erase(bst.find(nums[i - k - 1])); auto lb = bst.lower_bound(nums[i] - t); if (lb != bst.end() && *lb - nums[i] <= t) return true; bst.insert(nums[i]); } return false; } };