LeetCode219 ContainsDuplicateII java题解
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode219 ContainsDuplicateII java题解,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1374字,纯文字阅读大概需要2分钟。
内容图文
![LeetCode219 ContainsDuplicateII java题解](/upload/InfoBanner/zyjiaocheng/1099/babf6d5dbd0e4118938961bfe01f5886.jpg)
题目:
Given an array of integers and an integer
k
,
find out whether there 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^2)复杂度不能通过
第二种办法:
用哈希表,key存数组元素值,value存元素对应的索引,每来一个元素进行判断如果之前没有存过则存进去,如果之前有存则取出之前那个元素的索引值判断是否小于K,小于k返回true,不小于则存进去覆盖之前的那个。
代码:
public static boolean containsNearbyDuplicate(int[] nums, int k) { int length=nums.length; Hashtable<Integer, Integer> hashtable=new Hashtable<>(); for(int i=0;i<length;i++) { if(hashtable.get(nums[i])==null) { hashtable.put(nums[i], i); } else { int k1=hashtable.get(nums[i]); if(i-k1<=k) return true; else { hashtable.put(nums[i], i); } } } return false; }
第三种办法:用hashset,利用set集合中不能有重复的元素这个特性,也就是说如果之前set已经有这个值,执行添加操作的时候将不能成功添加,我们通过记录set的size大小就可以知道到底有没添加成功。我们维护一个动态变化大小为k+1的滑动窗口,当i小于k+1的时,只要有一次没添加成功,就返回true,当i大于等于k+1时,没添加一个元素之前先去除set中最早添加的那个元素。
代码:
public static boolean containsNearbyDuplicate2(int[] nums, int k) {
int length=nums.length;
Set<Integer> set=new HashSet<>();
for(int i=0;i<length;i++)
{
if(i<k+1)
{
set.add(nums[i]);
if(set.size()<i+1)
return true;
}
else {
set.remove(nums[i-k-1]);
set.add(nums[i]);
if(set.size()<k+1)
return true;
}
}
return false;
}
版权声明:本文为博主原创文章,未经博主允许不得转载。
原文:http://blog.csdn.net/u012249528/article/details/46729453
内容总结
以上是互联网集市为您收集整理的LeetCode219 ContainsDuplicateII java题解全部内容,希望文章能够帮你解决LeetCode219 ContainsDuplicateII java题解所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。