存在重复元素Ⅱ

2023-12-24 15:53:59

给你一个整数数组?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 <= 105
  • -109 <= nums[i] <= 109
  • 0 <= k <= 105
#哈希表
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        pos = {}
        for i, num in enumerate(nums):
            if num in pos and i - pos[num] <= k:
                return True
            pos[num] = i
        return False

#移动窗口
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        s = set()
        for i, num in enumerate(nums):
            if i > k:#如果i<k,当满足第二个if条件语句时,就可以得到True;如果i>k,就只保留区间长度(0,i-1),来满足 abs(i - j) <= k
                s.remove(nums[i - k - 1])
            if num in s:
                return True
            s.add(num)
        return False

文章来源:https://blog.csdn.net/hdnbnsnbns/article/details/135182020
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。