219. Contains Duplicate II

  • 31.8%

https://leetcode.com/problems/contains-duplicate-ii/

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.


方法一:

使用unordered_set,函数erase, insert

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
if(k==0 || nums.empty()) return false;
unordered_set<int> set;
for(int i=0; i<nums.size(); i++){
if(set.find(nums[i])!=set.end())
return true;
set.insert(nums[i]);
if(set.size()==k+1)
set.erase(nums[i-k]);
}
return false;
}
};

32ms, 47.64%, May.6th, 2016

https://leetcode.com/discuss/37851/c-solution-with-unordered_set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
unordered_set<int> s;

if(k <= 0) return false;
if(k >= nums.size()) k = nums.size() - 1;

for(int i = 0; i < nums.size(); i++){
if(i > k) s.erase(nums[i - k - 1]);
if(s.find(nums[i]) != s.end()) return true;
s.insert(nums[i]);
}
return false;
}
};

python


52ms, 56.23%, May.6th, 2016

https://leetcode.com/discuss/54123/python-concise-solution-with-dictionary

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def containsNearbyDuplicate(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: bool
"""
dic = {}
for i, v in enumerate(nums):
if v in dic and i - dic[v] <= k:
return True
dic[v] = i
return False

java


13ms, 44.06%, May.6th, 2016

https://leetcode.com/discuss/38445/simple-java-solution

1
2
3
4
5
6
7
8
9
10
public class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> set = new HashSet<Integer>();
for(int i = 0; i < nums.length; i++){
if(i > k) set.remove(nums[i-k-1]);
if(!set.add(nums[i])) return true;
}
return false;
}
}
谢谢你,可爱的朋友。