My C++ solution with detailed comments


  • 3
    A
    class Solution {
    public:
        bool containsNearbyDuplicate(vector<int>& nums, int k) {
            if (nums.size() == 0 || nums.size() == 1) { // if nums is empty or only contains one element, then we don't even have two indices to compare
                return false;
            }
            if (k == 0) { // i & j must be distinct
                return false;
            }
            map<int,int> hashMap; // hashMap to map from element to their indices in nums
            for (int i=0;i<nums.size();i++) {
                if (hashMap.find(nums[i]) != hashMap.end()) { // use find rather than subscripting the hashMap (if key not found, subscripting will automatically insert an unexisting key into the map with default value, which can lead to problems)
                    // if nums[i] has appeared once
                    if (i - hashMap.find(nums[i])->second <= k) { // if the distance between the 2 positions is less than k
                        return true;
                    }
                    else { // if the difference is bigger than k, update hashMap[num[i]] to i because i is the new closet position to future potential duplicates
                        hashMap[nums[i]] = i;
                    }
                }
                else {
                    hashMap.insert(pair<int,int>(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.