219_存在重复元素_II

类型：数组

• 219. 存在重复元素 II 💚

  https://leetcode-cn.com/problems/contains-duplicate-ii/

  ❓ 判断整数数组 nums 中是否存在 nums[i] = nums[j]，且 i, j 之差的绝对值小于等于 k。

  💡 哈希表 + 滑动窗口

  我们通过哈希表来维护一个大小为 k 的滑动窗口。

  遍历数组，针对每个元素做以下操作：

  • 在散列表中搜索当前元素，如果找到了就返回 true。
  • 在散列表中插入当前元素。
  • 如果当前散列表的大小超过了 k， 删除散列表中最旧的元素。

  class Solution:
      def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
          hashMap = {}
          for i in range(len(nums)):
              num = nums[i]
              if num in hashMap and i - hashMap[num] <= k:
                      return True
              else:
                  hashMap[num] = i
          return False

  时间复杂度：O(1)，空间复杂度：O(min(n, k))