给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。

这个题目花费了我不少时间，

首先暴力找他肯定要爆你的时间复杂度，所以我一开始的想法就是：

如果数组里面由两个相同的值，这两个相同的值的下标之差j-i<=k就能达到要求，那么我要是存在一个k+1的能满足要求呢，k+2的呢？如果我在k+1,k+2……之后找到了相同元素不就可以了吗，不过这样的时间复杂度也不小，一个元素至少1次

于是看看官方题解，说是建立一个长度为k的容器，然后装元素，一旦找到，就return true，如果没找到就return false

我的python代码如下

1
2
3
4
5
6
7
8
9
10
11
12
def func(nums,k):
    a = []
    for i in nums:
        if((i not in a) and (len(a)<k)):
            a.append(i)
        elif((i not in a) and len(a)==k):
            a.pop(0)
            a.append(i)
        elif(i in a):
            return True
       return False

我以为这就好了，每个元素只用读一次判断好几次就可以了，没想到，还是爆了时间复杂度，大约是因为len(a)这个函数还有in这个会占用一定的时间复杂度。因此再次查看题解，发现了一个很秀的解法

1
2
3
4
5
def func(nums,k):
    r, d = k + 1, {}
    for i, n in enumerate(nums):#i是下标，n是下标指向的元素
        r, d[n] = min(r, i - d.get(n, -k - 1)), i
    return r <= k

港真这个我看了好久，然后终于想明白了

i是每次的下标，然后如果找到了相同元素，当前下表（i）和相同元素的下标d.get(n)做差，然后就可以求得差值，最后同k进行比较即可