Contains Duplicate II

题目描述

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 difference between i and j is at most k.

解题方法

• 还是hashtable，保存上一次出现的index
• 每次又遇到的时候计算与上一次的距离，再将hashtable里的value更新为新的index

Solution

class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        if not nums:
            return False
        dic = {}
        for idx, num in enumerate(nums):
            if num in dic:
                dif = idx - dic[num]
                if dif <= k:
                    return True
            dic[num] = idx

        return False

Reference