Title:ExtractingTitle,Keywords,andSummaryfromContent

Leetcode 220. Contains Duplicate III (Medium) (cpp)

Tag: Binary Search Tree

Difficulty: Medium

/*
220. Contains Duplicate III (Medium)
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.
*/
class Solution {
public:
bool containsNearbyAlmostDuplicate(vector& nums, int k, int t) {
if (nums.size() <2) return false;
vector> withIndex;
for(int i = 0; i withIndex.emplace_back(nums[i], i);
sort(withIndex.begin(), withIndex.end(), [](const pair& a, const pair&b) { return a.first for(int i = 0; i int j = i + 1;
while(j if(withIndex[j].first - withIndex[i].first > t) break;
if(abs(withIndex[j].second-withIndex[i].second) <= k) return true;
j++;
}
}
return false;
}
};