《leetCode》：Contains Duplicate II

本文主要是介绍《leetCode》：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.

思路一：时间复杂度为O(n*k)

此题比较简单，利用两层for循环即可解决，值得注意的是限制条件是：j-i<=k；并不是j-i<=k+1;

bool containsNearbyDuplicate(int* nums, int numsSize, int k) {if(nums==NULL||numsSize<2){return false;}    for(int i=0;i<numsSize-1;i++){int temp=nums[i];int count=0;for(int j=i+1;j<numsSize;j++){count++;if(temp==nums[j]&&count<=k){//注意：至多为k，即j-i<=k;不是i和j两端都不算进去return true;}if(count>=k){break;}}}return false;
}

思路二：利用Set容器，时间复杂度为O(n)

实现代码如下：

public boolean containsNearbyDuplicate(int[] nums, int k) {if(nums==null||k<1){return false;}HashSet<Integer> hs=new HashSet<Integer>();for(int i=0;i<nums.length;i++){if(hs.add(nums[i])==false){//当此元素重复的时候，就不能放入Set容器中return true;}if(hs.size()==k+1){hs.remove(nums[i-k]);//就是删除此时hs中的第一个元素。}}return false;}

这篇关于《leetCode》：Contains Duplicate II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---