Straightforward solution, using C++ STL


  • 1
    Y
    bool containsNearbyDuplicate(vector<int>& nums, int k) 
    {
    	unordered_map<int,int> re;
    	for (int i = 0; i < nums.size(); i++)
    	{
    		if (re.find(nums[i]) != re.end() && i - re[nums[i]] <= k)return true;
    		else re[nums[i]] = i;
    	}
    	return false;
    }

  • 0
    Z
    This post is deleted!

  • 0
    G

    How about the nums is [1, 2, 3, 1, 3], k = 3? The program return true but actually it violates the question requirement which said there should be only one duplicate.


  • 0
    G

    Here is my modified solution which guarantees only one duplicate:

    class Solution {
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
            unordered_map<int, int> m;
            int d = 0;
            for (int i = 0; i < nums.size(); ++i) {
                if (m.find(nums[i]) != m.end()) {
                    if (d > 0) return false;
                    d = i - m[nums[i]];
                }
                m[nums[i]] = i;
            }
            return d == 0 ? false : d <= k;
        }
    };

  • 0
    Y

    Thanks, actually i noticed this at first time, but it got ACed, maybe your test case should be added.
    for your code, [1,2,3,1] k=3, your program will return false?


  • 0
    G

    nums = [1, 2, 3, 1], k = 3, my program return true. Because d = 3, and d <= k is true


  • 0

    Did they change the question? Because it doesn't say that there should be only one duplicate.


Log in to reply
 

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