Java实现LeetCode(1.两数之和)
作者:NullPointerExcept 发布时间:2021-06-03 02:11:19
标签:Java,LeetCode,两数之和
给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回[0, 1]
思路一:最直接的思维,两次遍历查询,时间复杂度O(N*N)。
代码:
public static int[] twoSum1(int[] nums, int target) {
int[] label = new int[2];
for(int i=0;i<nums.length-1;i++) {
int tmp = target - nums[i];
for(int j=i+1;j<nums.length;j++) {
if(tmp == nums[j]) {
label[0] = i;
label[1] = j;
}
}
}
return label;
}
思路二:先排序,然后两个指针i,j,i从前开始,j从后开始查找,当nums[i]+nums[j]>target时,j--;当nums[i]+nums[j]<target时,i++;注意排序后,之前的下标数字已经变化了。时间复杂度O(N*Log2N)
代码:
public static int[] twoSum2(int[] nums, int target) {
int[] label = new int[2];
int[] tmpArr = new int[nums.length];
for(int i=0;i<nums.length;i++) {
tmpArr[i]=nums[i];
}
Arrays.sort(nums);
int i=0;
int j=nums.length-1;
while (i<j) {
if(nums[i]+nums[j]==target) {
label[0] = nums[i];
label[1] = nums[j];
break;
}else if(nums[i]+nums[j]>target){
j--;
}else {
i++;
}
}
for(int k=0;k<tmpArr.length;k++) {
if(tmpArr[k]==label[0]) {
label[0]=k;
}
if(tmpArr[k]==label[1]) {
label[1]=k;
}
}
return label;
}
思路三:利用空间换时间方式,用hashmap存储数组结构,key为值,value为下标。时间复杂度O(N)。
代码:
public static int[] twoSum3(int[] nums, int target) {
int[] label = new int[2];
HashMap<Integer, Integer> hashMap = new HashMap<>();
for(int i=0;i<nums.length;i++) {
hashMap.put(nums[i], i);
}
for(int i=0;i<nums.length;i++) {
if(hashMap.containsKey(target-nums[i])&&hashMap.get(target-nums[i])!=i) {
label[0] = i;
label[1] = hashMap.get(target-nums[i]);
break;
}
}
return label;
}
github地址:https://github.com/xckNull/Algorithms-introduction
来源:https://blog.csdn.net/jek123456/article/details/79989145


猜你喜欢
- 本文实例讲述了WinForm实现的图片拖拽与缩放功能。分享给大家供大家参考,具体如下:最近做项目的时候遇到上传施工平面布置图,查看,因为图片
- 一、@RestController 注解在 Spring Boot 中的 Controller 中使用 @RestController 注解
- 前言现在有这么个需求,网上购物,需要根据不同的规则计算商品折扣,比如VIP客户增加5%的折扣,购买金额超过1000元的增加10%的折扣等,而
- 本文实例汇总了Java各种排序算法。分享给大家供大家参考,具体如下:1. 冒泡排序:public class SortTest { pub
- 封装在如何理解面向对象这篇文章中,提到所谓的封装就是“功能都给你做好了,你不必去理解它是怎么写出来的,直接使用即可。”。但你得清楚一点,那就
- 最近学习了继承,多态,集合,设计模式,有一个汽车租凭系统,给大家分享一下:我们首先来看看我们这个系统的效果1.做一个项目,我们首先对项目进行
- 目录前言一、Android应用DAC沙盒二、Android应用权限三、应用信息的存储四、应用权限的映射五、应用的SELinux标签六、And
- .NETCORE 中的 Generic Host本文以自己在工作中学习和使用.net core generic-host 作一个总结。前言在
- Struts2中提供了数据校验验证数据例如验证邮件、数字等。验证方式有3种:一是通过validate()方法,二是通过Xml,三是使用注解方
- Java xml出现错误 javax.xml.transform.TransformerException: java.lang.NullP
- 目录例1: 以下代码输出什么?例2: 为什么虚函数效率低?虚继承例3: 请评价多重继承的优点和缺陷。例4: 在多继承的时候,如果一个类继承同
- 本文实例讲述了C#动态加载dll扩展系统功能的方法。分享给大家供大家参考。具体分析如下:动态加载dll,主要是为了扩展功能,增强灵活性而实现
- 本文实例讲述了C#实现启动,关闭与查找进程的方法。分享给大家供大家参考,具体如下:运行效果截图如下:查找/列出进程很容易,但干掉进程得借助系
- 本文实例讲述了C#按字节数截取字符串并在后面加上省略号...的方法,这是一个自定义的C#函数,函数的使用说明如下:<param nam
- MSMQ (Microsoft消息队列)是Windows中默认可用的消息队列。作为跨计算机系统发送和接收消息的可靠方法,MSMQ提供了一个可
- 本示例演示如何通过设置Intent对象的标记,来改变当前任务堆栈中既存的Activity的顺序。1. Intent对象的Activity启动
- 1.背景Java语言相比于C和C++,一个最大的特点就是不需要程序员自己手动去申请和释放内存,这一切交由JVM来完成。在Java中,运行时的
- 上周,公司的项目改版要求加上一个右滑返回上一个界面,于是就在网上找了一些开源库打算实现.但是在使用的时候遇见了许多的问题.试了两天用过 ht
- 本文实例讲述了C#设计模式之Facade外观模式解决天河城购物问题。分享给大家供大家参考,具体如下:一、理论定义外观模式 &nbs
- 我本地的springboot版本是2.5.1,后面的分析都是基于这个版本 <parent> &nbs