LeetCode 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 <= 10^5
• -109 <= nums[i] <= 10^9
• 0 <= k <= 10^5

二、题目解析

三、参考代码

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:

        # 使用哈希集合
        pos = {}

        # 如果想在 for 循环中同时获得列表的索引 i 和元素值 v
        # 可以使用枚举内置函数 enumerate()
        for i, v in enumerate(nums):
            # 1、如果发现当前这个元素 v 已经存在于哈希集合里面
            # 说明在此之前就已经访问到了一个元素，值为 v
            # 2、pos[v] 表示的是之前访问到的元素值所在的索引
            # 判断 i - pos[v] <= k
            if v in pos and i - pos[v] <= k:
                # 符合要求，就返回 True
                return True
            # 否则，把 v 和 i 存储到哈希集合里面
            pos[v] = i

        # 最终没有找到，返回 False
        return False