存在重复元素Ⅱ
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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!