Contains Duplicate II

Question

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Tags

• Array
• Hashmap

Thought

Use a dictionary to record the number and the corresponding index in the nums. Then if the number is already in the dictionary, compare the absolute difference between index and the value in the dictionary with the integer k.

Code

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        numDict = dict()
        for i, num in enumerate(nums):
            if num not in numDict:
                numDict[num] = i
            else:
                if i - numDict[num] <= k:
                    return True
                else:
                    numDict[num] = i
        return False