跳至主要內容

0219. 存在重复元素 II

ITCharge大约 1 分钟

0219. 存在重复元素 IIopen in new window

  • 标签:数组、哈希表、滑动窗口
  • 难度:简单

题目链接

题目大意

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

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

说明

  • 1nums.length1051 \le nums.length \le 10^5
  • 109<=nums[i]<=109-10^9 <= nums[i] <= 10^9
  • 0k1050 \le k \le 10^5

示例

  • 示例 1:
输入:nums = [1,2,3,1], k = 3
输出:True

解题思路

思路 1:哈希表

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

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

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

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

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

思路 1:代码

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        nums_dict = dict()
        for i in range(len(nums)):
            if nums[i] in nums_dict:
                return True
            nums_dict[nums[i]] = 1
            if len(nums_dict) > k:
                del nums_dict[nums[i - k]]
        return False

思路 1:复杂度分析

  • 时间复杂度O(n)O(n)
  • 空间复杂度O(n)O(n)