O(n) simple solution in C++ using unordered_map and C# using dictionary


  • 0
    O

    C++ version

    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        if(nums.size() > 1){
            //create a hashtable with key = nums[i] and value = i
            unordered_map<int, int> dic;
            for(int i = 0; i <nums.size(); ++i)
            {
                unordered_map<int, int>::iterator indice = dic.find(nums[i]);
                // if indice exist, compare with the new one
                if(indice != dic.end() && (i - indice->second) <= k)
                {
                    return true;
                }
                else
                {
                    // set the new indice
                    dic[nums[i]] = i;
                }
            }
        }
        
        return false;        
    }
    

    C# version

    public bool ContainsNearbyDuplicate(int[] nums, int k) {
        if(nums != null && nums.Length > 1){
            //create a hashtable with key = nums[i] and value = i
            Dictionary<int, int> dic  = new Dictionary<int, int>();
            for(int i = 0; i <nums.Length; ++i)
            {
                int indice;
                // if indice exist, compare with the new one
                if(dic.TryGetValue(nums[i], out indice) && (i - indice <= k))
                {
                    return true;
                }
                else
                {
                    // set the new indice
                    dic[nums[i]] = i;
                }
            }
        }
        
        return false;
    }

Log in to reply
 

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