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

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

2021-06-26 13:51sdr_zd 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<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;

									  }

									}