20 ms hybrid solution, brute force if k is small, otherwise sort, n*k or n*log(n) complexity

• ``````class Solution {
struct myNode{ int val, ind; };
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
if(nums.size()<2) return false;
if(k<=12) {
for(int i=k,j,val;i<nums.size();++i) {
for(val=nums[i], j=i-k;nums[j]!=val;++j) {}
if(j<i) return true;
}
auto pend=nums.begin()+std::min(k,(int)nums.size());
std::sort(nums.begin(),pend);
}
vector<myNode> num_and_ind(nums.size());
for(int i=0;i<nums.size();++i) {
num_and_ind[i].val=nums[i];
num_and_ind[i].ind=i;
}
std::sort(num_and_ind.begin(),num_and_ind.end(),[](const myNode lhs,const myNode rhs) { return lhs.val<rhs.val || lhs.val==rhs.val && lhs.ind<rhs.ind; });
auto p=&num_and_ind[0], pend=&num_and_ind[num_and_ind.size()];
for(auto next=p+1;next!=pend;++p,++next) {
if(p->val==next->val && next->ind-p->ind<=k) return true;
}
return false;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.