Java查找不重复无序数组中是否存在两个数字的和为某个值
作者:sdr_zd 发布时间:2023-08-22 16:44:40
标签: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;
}
}
来源:https://blog.csdn.net/sdr_zd/article/details/82904396
0
投稿
猜你喜欢
- 通常情况下我们想实现文字的走马灯效果需要在xml文件中这样设置<TextView android:layout_widt
- 首先先简单的说一下其3大特性的定义:封装:隐藏对象的属性和实现细节,仅对外公开接口,控制在程序中属性的读和修改的访问级别。将抽象得到的数据和
- 假如是在同一台机器上开发,前后端分离的工程中出现跨域问题的原因是,前端工程和后端工程运行在不同的端口上。只要协议、域名、端口有一个不同就会产
- 前言多数据源的事务处理是个老生常谈的话题,跨两个数据源的事务管理也算是分布式事务的范畴,在同一个JVM里处理多数据源的事务,比较经典的处理方
- 本文实例讲述了C#启动进程的几种常用方法。分享给大家供大家参考。具体如下:1.启动子进程,不等待子进程结束private void simp
- 由于我们在eclipse ee中把项目部署在web端经常会出现报404错误。原因为:404状态码是一种http状态码,其意思是: 所请求的页
- 一、前言在Spring中,事务有两种实现方式:编程式事务管理: 编程式事务管理使用TransactionTemplate可实现更细
- 实例如下:import java.lang.reflect.Field;import java.lang.reflect.Invocatio
- 什么是volatile关键字volatile是Java中用于修饰变量的关键字,其可以保证该变量的可见性以及顺序性,但是无法保证原子性。更准确
- 前言空间分配要点有:一是空间分配的连续性;二是动态内存申请;三是防止程序执行中出现异常错误。提示:开始讲解了嗷~后续会根据精力持续更新嗷!!
- 1.需求背景需要实现一个动态加载但不显示出来的视图,且该视图上有个动态生成的二维码,最后用其去生成一张快照(也就是图片)。(常见这种情况是来
- 本文实例讲述了Java Web项目部署在Tomcat运行出错与解决方法。分享给大家供大家参考,具体如下:1、在部署Java Web项目的过程
- java 网络编程java.net 类 InetAddress 此类表示互联网协议 (IP) 地址。 会抛出异常 UnknownHostEx
- 1、首先导入solrj需要的的架包2、需要注意的是低版本是solr是使用SolrServer进行URL实例的,5.0之后已经使用SolrCl
- 要想实现android手机通过扫描名片,得到名片信息,可以使用脉可寻提供的第三方SDK,即Maketion ScanCard SDK,脉可寻
- 本文实例为大家分享了Struts2框架拦截 器实例的示例代码,供大家参考,具体内容如下在看拦截 器的小例子的前我们先来看看sturts2的原
- SingleClick:@Retention(AnnotationRetention.RUNTIME)@Target(AnnotationT
- 需求说明实际操作过程中,从D盘根目录下的ak.txt读取文件写入D盘根目录下的hello.txt文件内实现思路写两个方法,一个用于读取目标文
- 本文实例讲述了Java实现接口的枚举类。分享给大家供大家参考,具体如下:一 点睛枚举类也可以实现一个或多个接口。与普通类实现一个或多个接口完
- 前言很多时候,当你以为掌握了事实真相的时间,如果你能再深入一点,你可能会发现另外一些真相。比如面向切面编程的最佳编程实践是AOP,AOP的主