My Accepted O(n) Solution -> simplify this problem into Contain Duplicate II

• ``````class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
if (nums.size() < 2) return false;
if (t < 0) return false;

map<int, int> m1;
map<int, int> m2;

for (int i = 0; i < nums.size(); i++){
int num1 = nums[i] >= 0 ? nums[i]/(t+1) : nums[i]/(t+1) - 1;
if (m1.count(num1) && m1[num1] >= i - k)   return true;
m1[num1] = i;

int num2 = nums[i] >= 0 ? (nums[i] + (t+2) / 2 )/(t+1) : (nums[i] + (t+2) / 2 )/(t+1) - 1;
if (m2.count(num2) && m2[num2] >= i - k)   return true;
m2[num2] = i;
}

return false;
}
};``````

• It may not work for [5,7], 2, 2. In the first dictionary, we got m1[1] = 0 and m1[2] = 1 and in the second dictionary, we got m2[2] =0 and m2[3] =1

Please tell me where I was wrong...
Thanks!

• Hi ! I think you are right! I think it gets around in Leetcode's testing then, it got accepted......but thank you for pointing this case out ! This is very good !!

is there anyway we can modify this code around to make it work?

• Hi, sorry I don't know.... I think it depends on the remains after nums[i] divided by (t+1).

• ``````class Solution {
public:
bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
if (nums.size() < 2) return false;
if (t < 0) return false;

unordered_map<int, int> m1;
for (int i = 0; i < nums.size(); i++){
int num1 = nums[i] >= 0 ? nums[i]/(t+1) : nums[i]/(t+1) - 1;
if (m1.count(num1) && m1[num1] >= i - k)   return true;
m1[num1] = i;
if(m1.count(num1+1))
{
if(labs((long)nums[i]-nums[m1[num1+1]])<=(long)t&&m1[num1+1] >= i - k)return 1;
}
if(m1.count(num1-1))
{
if(labs((long)nums[i]-nums[m1[num1-1]])<=(long)t&&m1[num1-1] >= i - k)return 1;
}

}

return false;
}

};``````

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