首页 > 开发 > Java > 正文

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

2019-10-21 18:41:52
字体:
来源:转载
供稿:网友

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

  1. 给定一个不重复的无序数组arr和一个定值num
  2. 查找arr中是否有两个数的和等于num
  3. 有则返回这两个数的下标(可能有多组, 只用返回一组), 没有则返回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;  }}

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对CuoXin错新网的支持。


注:相关教程知识阅读请移步到JAVA教程频道。
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表