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.

思路

首先想到的是用两个指针，只要两个指针指向的值相等，就求出两个指针指向的值之差。但是这样的操作，其实最后的复杂度相对来说会高一些。另外要注意，题目提到，两个相等的数之间差值是“至多”为k，而不是“恰好“为k。

这一部分代码是之前用两个指针的方法，得到了错误的答案。

1
2
3
4
5
6
7
8
length = len(nums)
if (k >= len(nums)):
    return False
else:
    for i in range(length-k):
        if(nums[i] == nums[i+k]):
            return True
    return False

需要注意，只要有一组数字满足要求，函数就应该返回真。
要想将复杂度降低，需要利用哈希表来进行操作。在遍历数组的时候，同时将数组的数值加入哈希表中，从而可以利用它来求得题意所需的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def containsNearbyDuplicate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        length = len(nums)
        kmap = {}
        for i in range(length):
            if (kmap.has_key(nums[i])):
                if (i - kmap[nums[i]] <= k):
                    return True
                else:
                    kmap[nums[i]] = i
            else:
                kmap[nums[i]] = i
        return False