题目

给定一个整数数组和一个整数 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

方案一（双指针）

  1. class Solution:
  2.     def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
  3.         # 滑动窗口(双指针)
  4.         for i in range(len(nums)):
  5.             j = i + 1
  6.             while j - i <= k and j < len(nums):
  7.                 if nums[i] == nums[j]:
  8.                     return True
  9.                 j += 1
  10.             i += 1
  12.         return False
  • 每次固定指针i，然后移动指针j到window的大小，检查有没有重复的；
  • 时间复杂度存在重复元素 II - 图1
  • 空间复杂度存在重复元素 II - 图2

    方案二（set）

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        # set
        if len(nums) <= 1 or k == 0:
            return False

        st = set(nums[:k + 1]) # 前 k + 1 个元素放入 set
        if len(nums) <= k and len(st) == len(nums): # k 比数组长度长
            return False
        if len(st) <= k:  # 前k个有重复的
            return True

        # 循环一次，每次移除最前面的指针，并加上最后的指针
        i = k + 1
        while i < len(nums):
            st.remove(nums[i - k - 1])
            if nums[i] in st:
                return True
            st.add(nums[i])
            i += 1

        return False
  • 首先将前k+1个元素放入集合st中，如果st长度小于等于k说明前k+1个元素中有重复元素；否则移动指针，每次移除最前面的元素，然后看最新的元素是否在集合中，如果存在则说明存在重复元素。
  • 注意特殊情况处理
  • 时间复杂度存在重复元素 II - 图3
  • 空间复杂度存在重复元素 II - 图4

leetcode 代码，思路一致

class Solution:
    def containsNearbyDuplicate(self, nums: [int], k: int) -> bool:
        n = len(nums)
        if (n <= 1): return False

        recode = set()
        for i in range(n):
            if nums[i] in recode:
                return True
            recode.add(nums[i])
            if len(recode) > k:
                recode.remove(nums[i - k])

        return False

方案三（leetcode方案）

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