0219. 存在重复元素 II

0219. 存在重复元素 II #

  • 标签:数组、哈希表
  • 难度:简单

题目大意 #

描述:给定一个整数数组 nums 和一个整数 k

要求:判断是否存在 $nums[i] == nums[j](i \ne j)$,并且 ij 的差绝对值至多为 k

说明

  • $1 \le nums.length \le 10^5$。
  • $-10^9 <= nums[i] <= 10^9$。
  • $0 \le k \le 10^5$。

示例

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

解题思路 #

思路 1:哈希表 #

维护一个最多有 k 个元素的哈希表。遍历 nums,对于数组中的每个整数 nums[i],判断哈希表中是否存在这个整数。

  • 如果存在,则说明出现了两次,且 $i \ne j$,直接返回 True

  • 如果不存在,则将 nums[i] 加入哈希表。

  • 判断哈希表长度是否超过了 k,如果超过了 k,则删除哈希表中最旧的元素 nums[i - k]

  • 如果遍历完仍旧找不到,则返回 False

思路 1:哈希表代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        nums_set = set()
        for i in range(len(nums)):
            if nums[i] in nums_set:
                return True
            nums_set.add(nums[i])
            if len(nums_set) > k:
                nums_set.remove(nums[i - k])
        return False
本站总访问量  次  |  您是本站第  位访问者