Leetcode 220.Contains duplicate III 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.
// 时间复杂度: O(nlogn)
// 空间复杂度: O(k)
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
set<long long> record;//二叉树查找表 有序
for( int i = 0 ; i < nums.size() ; i ++ ){
if( record.lower_bound( (long long)nums[i] - (long long)t ) != record.end() &&
*record.lower_bound( (long long)nums[i] - (long long)t ) <= (long long)nums[i] + (long long)t ) {
return true;
}
record.insert( nums[i] );
if( record.size() == k + 1 )
record.erase( nums[i-k] );
}
return false;
}
};
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
set<int> window; // set is ordered automatically
for (int i = 0; i < nums.size(); i++) {
if (i > k) window.erase(nums[i-k-1]); // keep the set contains nums i j at most k
// |x - nums[i]| <= t ==> -t <= x - nums[i] <= t;
auto pos = window.lower_bound(nums[i] - t); // x-nums[i] >= -t ==> x >= nums[i]-t
// x - nums[i] <= t ==> |x - nums[i]| <= t
if (pos != window.end() && *pos - nums[i] <= t) return true;
window.insert(nums[i]);
}
return false;
}