Short C++ solution


  • 15
    D
    class Solution {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            map<long long,int> M;
            int l=0;
            for (int r=0;r<nums.size();r++) {
                if (r-l>k && M[nums[l]]==l)
                    M.erase(nums[l++]);
                auto it=M.lower_bound(nums[r]-t);
                if (it!=M.end() && abs(it->first-nums[r])<=t)
                    return true;
                M[nums[r]]=r;
            }
            return false;
         }
    };

  • 1
    R
    if (r-l>k && M[nums[l]]==l)
    

    the second judgement statement seems needless, cos every time u assign the map with M[nums[r]]=r;
    anyway it's an excellent solution though~~


  • 0
    O

    is that a problem that the second judgement still there but without a check in if (it!=M.end() && abs(it->first-nums[r])<=t) about the interval? will it return a wrong answer since the interval already excess k?


  • 2
    F

    Hi! This is my solution. Share the same idea with you.

    class Solution {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            map<int, int> m;
            for(int i = 0; i < nums.size(); ++i) {
                auto it = m.lower_bound(nums[i] - t);
                while(it != m.end() && it->second < i - k)  it = m.erase(it);
                if(it != m.end() && nums[i] >= it->first - t) 
                    return true;
                m[nums[i]] = i;
            }
            return false;
        }
    };

  • 0
    J

    @fastcode I change you solution,It can not pass the case
    [-2147483648,-2147483647]
    3
    3
    code here:

    class Solution {
    public:
        bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
            map<long long, int> map;
        	for (int i = 0; i < nums.size(); ++i)
        	{
        		auto it = map.lower_bound((long long)nums[i] - (long long)t);
        		while (it != map.end() && i - it->second > k)
        			it = map.erase(it);
        		if (it != map.end() && abs(nums[i] - it->first) <= t)
        			return true;
        		map[nums[i]] = i;
        	}
        	return false;
        }
    };
    

  • 0
    S

    @fastcode your solution is wrong


Log in to reply
 

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