今天去某在线教育面试面试官让做的一道题，题目描述如下：
给定一个不重复的无序数组arr和一个定值num 查找arr中是否有两个数的和等于num 有则返回这两个数的下标(可能有多组, 只用返回一组), 没有则返回null很多人一想可能就是两层for循环，我想了很久最后写了双重for循环…【这个代码太easy就不放了】然后面试官说知道哈希吗，由于哈希查找的时间复杂度是o(1)，从哈希的角度去考虑，这中间还有一堆就不描述了，说一下怎么用哈希实现。
实现思路：
将数组中的所有的值放入hashmap的key中，value存放该值对应的下标，遍历这个hashmap，取得key，计算如果可以和这个key加起来的和为num的值，如果这个值存在，就直接返回这两个下标。遍历一次的时间复杂度为o(n)，查找的时间复杂度是o(1)，总体时间复杂度o(n)。
代码实现：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
public class gettwonumssumequals { public static void main(string[] args) { int [] arr = new int []{ 3 , 4 , 6 , 5 , 9 , 8 }; int num = 8 ; int [] ret = getindex(arr, num); system.out.println( "index of two numbers r:" + ret[ 0 ] + " " + ret[ 1 ]); } // 找到这两个数的下标并返回（以长度为2的数组的形式返回） private static int [] getindex( int [] arr, int num) { int [] ret = new int [ 2 ]; hashmap<integer, integer> hashmap = new hashmap<>(); int index = 0 ; // 将每个数字和其下标放进map中 for (integer curr : arr) { hashmap.put(curr, index++); } // 遍历hashmap并判断 for (map.entry<integer, integer> entry : hashmap.entryset()) { int value = entry.getkey(); int subvalue = num - value; if (hashmap.containskey(subvalue)) { // 找到啦! ret[ 0 ] = entry.getvalue(); ret[ 1 ] = hashmap.get(subvalue); break ; } } return ret; } } |
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对的支持。如果你想了解更多相关内容请查看下面相关链接
原文链接：https://blog.csdn.net/sdr_zd/article/details/82904396
查看更多关于Java查找不重复无序数组中是否存在两个数字的和为某个值的详细内容...