Java查找不重复无序数组中是否存在两个数字的和为某个值
今天去某在线教育面试面试官让做的一道题，题目描述如下：
- 给定一个不重复的无序数组arr和一个定值num
- 查找arr中是否有两个数的和等于num
- 有则返回这两个数的下标(可能有多组,只用返回一组),没有则返回null
很多人一想可能就是两层for循环，我想了很久最后写了双重for循环…【这个代码太easy就不放了】然后面试官说知道哈希吗，由于哈希查找的时间复杂度是O(1)，从哈希的角度去考虑，这中间还有一堆就不描述了，说一下怎么用哈希实现。
实现思路：
将数组中的所有的值放入HashMap的Key中，Value存放该值对应的下标，遍历这个HashMap，取得Key，计算如果可以和这个Key加起来的和为num的值，如果这个值存在，就直接返回这两个下标。遍历一次的时间复杂度为O(N)，查找的时间复杂度是O(1)，总体时间复杂度O(N)。
代码实现：
publicclassgetTwoNumsSumEquals{
publicstaticvoidmain(String[]args){
int[]arr=newint[]{3,4,6,5,9,8};
intnum=8;
int[]ret=getIndex(arr,num);
System.out.println("indexoftwonumbersR:"+ret[0]+""+ret[1]);
}
//找到这两个数的下标并返回（以长度为2的数组的形式返回）
privatestaticint[]getIndex(int[]arr,intnum){
int[]ret=newint[2];
HashMaphashMap=newHashMap<>();
intindex=0;
//将每个数字和其下标放进map中
for(Integercurr:arr){
hashMap.put(curr,index++);
}
//遍历HashMap并判断
for(Map.Entryentry:hashMap.entrySet()){
intvalue=entry.getKey();
intsubValue=num-value;
if(hashMap.containsKey(subValue)){
//找到啦!
ret[0]=entry.getValue();
ret[1]=hashMap.get(subValue);
break;
}
}
returnret;
}
}
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对毛票票的支持。如果你想了解更多相关内容请查看下面相关链接