Contains Duplicate III 下标范围<=k 值范围<=t

时间:2023-11-28 23:54:32

set妙用

1、维护一个大小最大位k的set set中数据是有顺序的

2、每次新加一个数据,只需要比较该数据加入 有没有带来变化

3、找到 >= 新数据-t的数据对应的迭代器 pos

4、如果找到了 pos != window.end(),并且该数据不大于当前数据+t( *pos - nums[i] <= t) ,则返回正确

5、该代码有缺陷,最好将数据变为long,再进行比较

 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
auto pos = window.lower_bound(nums[i] - t);
if (pos != window.end() && *pos - nums[i] <= t) return true;
window.insert(nums[i]);
}
return false;
}