Java查找不重复无序数组中是否存在两个数字的和为某个值

Java查找不重复无序数组中是否存在两个数字的和为某个值

今天去某在线教育面试面试官让做的一道题，题目描述如下：

给定一个不重复的无序数组arr和一个定值num

查找arr中是否有两个数的和等于num

有则返回这两个数的下标(可能有多组, 只用返回一组), 没有则返回null

很多人一想可能就是两层for循环，我想了很久最后写了双重for循环…【这个代码太easy就不放了】然后面试官说知道哈希吗，由于哈希查找的时间复杂度是O(1)，从哈希的角度去考虑，这中间还有一堆就不描述了，说一下怎么用哈希实现。

实现思路：

将数组中的所有的值放入HashMap的Key中，Value存放该值对应的下标，遍历这个HashMap，取得Key，计算如果可以和这个Key加起来的和为num的值，如果这个值存在，就直接返回这两个下标。遍历一次的时间复杂度为O(N)，查找的时间复杂度是O(1)，总体时间复杂度O(N)。

代码实现：

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 hashMap = new HashMap<>();

int index = 0;

// 将每个数字和其下标放进map中

for (Integer curr : arr) {

hashMap.put(curr, index++);

}

// 遍历HashMap并判断

for (Map.Entry 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;

http:// }

}

return ret;

}

}

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对我们的支持。如果你想了解更多相关内容请查看下面相关链接

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。