力扣第219题-存在重复元素II

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

 

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：true
示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true
示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
输出：false

提示：

1 <= nums.length <= 105
-109 <= nums[i] <= 109
0 <= k <= 105

2.1 方法一：暴力滑动窗口

这种思路很简单，就是使窗口大小为 2 ~ len(nums) - 1，然后让窗口向后滑动，寻找满足条件的数据。

但是！！！这种方法毫无疑问时间复杂度过高！

代码实现:

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # 方法一:滑动窗口
        for window_width in range(1, len(nums)):
            for i in range(len(nums) - window_width):
                if nums[i] == nums[i + window_width] and window_width <= k:
                    return True
        return False

2.2 哈希表

下面有请我们的老朋友--哈希表。

思路是这样的：我们遍历一遍nums列表，注意需要使用到index和值，如果列表元素不在哈希表中或者 （列表元素在哈希表中）但是当前的索引-这个元素在哈希表中对应的值（其实就是旧的index）大于k，那么说就让hashmap[num] = index，将值和index存进哈希表中或者进行更新，否则的话（这个元素在哈希表中并且索引的差值小于等于k，那么正好满足条件）。

代码实现：

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # 方法二：哈希表
        hashmap = {}
        for index, num in enumerate(nums):
            if num in hashmap and index - hashmap[num] <= k:
                return True
            hashmap[num] = index
        return False

注意：上述代码参考力扣官方题解！

遇到数组相关的难题，可以思考使用哈希表，往往会有很好的效果。