文章作者：Tyan
博客：noahsnail.com | CSDN | 简书
1. Description
Contains Duplicate III
2. Solution
- Version 1
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
if(nums.size() > 10000) {
return false;
}
for(int i = 0; i < nums.size(); i++) {
for(int j = i + 1; j < nums.size(); j++) {
long long diff = 0;
diff = llabs(diff + nums[j] - nums[i]);
if(diff <= t && j - i <= k) {
return true;
}
}
}
return false;
}
};
- Version 2
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
map<long long, int> m;
int index = 0;
for(int i = 0; i < nums.size(); i++) {
if(i - index > k) {
m.erase(nums[index++]);
}
auto pair = m.lower_bound((long long)nums[i] - t);
if(pair != m.end() && llabs(pair->first - nums[i]) <= t) {
return true;
}
m[nums[i]] = i;
}
return false;
}
};
