Leetcode 219. 存在重复元素 II

题目描述

给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。

示例 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

题意为，若在 k+1 个长度的子数组中存在两个元素相同，则返回 true，否则返回 false。

解法

以滑动窗口形式来判断窗口覆盖范围内是否存在两个元素相等。因为要判断元素是否存在，所以这里使用 set 集合作为窗口覆盖元素的存储结构。

若使用数组作为存储结构，当 k 较大时，可能会存在计算超时情况。

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        if k==0:
            return False
        s=set()
        for i in range(len(nums)):
            if nums[i] in s:
                return True
            if i-k>=0:
                s.remove(nums[i-k])
            s.add(nums[i])
        return False