塞进裤子ヾ(≧O≦)〃嗷~

0%

leetcode-219存在重复元素II

最初想法:

排好序,在k个元素里找相同的,这种思路是错的。

method2:暴力法,比较相邻k个元素,超时

1
2
3
4
5
6
7
8
9
10
11
def containsDuplicate(nums,k):
for i in range(len(nums)):
if i+k <= len(nums)-1:
mycount = k
else:
mycount = len(nums)-1 - i

for j in range(1,mycount+1):
if nums[i] == nums[i+j]:
return True
return False

Method3: 维护一个大小为k的set,里面始终最多包含 k 个元素,当出现重复值时则说明在 k 距离内存在重复元素。
每次遍历一个元素则将其加入set中,如果set的大小大于 k,则移除最前面的数字.

最终版本

1
2
3
4
5
6
7
8
9
def containsDuplicate(nums,k):
myset = set()
for i in range(len(nums)):
if nums[i] in myset:
return True
myset.add(nums[i])
if len(myset)>k:
myset.remove(nums[i-k])
return False
if help:小手一抖点个广告 or 大手一挥资助一下